Cod sursa(job #2387488)

Utilizator TeoDiDiaconescu Teodora TeoDi Data 24 martie 2019 19:13:48
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <string.h>
#define nMax 2000001
#define mMax 2000001
using namespace std;
ifstream fin("KMP.in");
ofstream fout("KMP.out");

int Urm[mMax];
char T[nMax],P[mMax];
int n,m;

void KMP(char *P)
{
    int k=-1,x;
    Urm[0]=0;
    for(x=1;x<m;x++)
    {
        while(k>0 && P[k+1]!=P[x]) k=Urm[k];
        if(P[k+1]==P[x]) k++;
        Urm[x]=k;
    }
}
int main()
{
    int i,x=-1;
    fin.getline(P,2000000);
    fin.getline(T,2000000);
    n=strlen(T); m=strlen(P);
    KMP(P);
    int ct=0;
    int v[200000];
    for(i=0;i<n;i++)
    {
        while(x>0 && P[x+1]!=T[i]) x=Urm[x];
        if(P[x+1]==T[i]) x++;
        if(x==m-1)
        {
            v[++ct]=i-m+1;
            x=Urm[x];
        }
    }
    fout<<ct<<'\n';
    for(int i=1;i<=ct;i++) fout<<v[i]<<' ';
    return 0;
}