Cod sursa(job #1798362)

Utilizator DavidDragulinDragulin David DavidDragulin Data 5 noiembrie 2016 10:37:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <string.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char N[2000000],M[2000000],x;
int i,n,m,k,q;
int urm[2000000],v[2000000];
int main()
{
    fin>>N;
    fin>>M;
    n=strlen(N);
    m=strlen(M);
    for(i=2;i<=n;i++)
    {
        while(k>0&&N[i-1]!=N[k])
            k=urm[k];
        if(N[i-1]==N[k])
            k++;
        urm[i]=k;
    }
    k=0;
    for(i=0;i<m;i++)
    {
        while(q>0&&M[i]!=N[q])
            q=urm[q];
        if(M[i]==N[q])
            q++;
        if(q==n)
        {
            k++;
            v[k]=i-n+1;
            if(k==1000)
                break;
        }
    }
    fout<<k<<'\n';
    for(i=1;i<=k;i++)
        fout<<v[i]<<" ";
    return 0;
}