Cod sursa(job #929534)

Utilizator VladMSBonta vlad valentin VladMS Data 27 martie 2013 08:14:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
//KNUTH�MORRIS�PRATT ALGORITHM
#include <fstream>
#include <cstring>
#define NMAX 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i,j,n1,n2,rez[NMAX],k,ok,l[NMAX],p;
long long nr;
char s1[NMAX],s2[NMAX];
int main()
{
    fin.get(s2,NMAX);
    fin.get();
    fin.get(s1,NMAX);
    n1=strlen(s1);
    n2=strlen(s2);
    if(n2>n1)
        fout<<0<<'\n';
    else
    {
        for(i=0;i<n2;++i)
            l[i]=-1;
        for(p=1;p<n2;++p)
        {
            k=l[p-1];
            while(k>=0&&s2[k+1]!=s2[p])
                k=l[k];
            if(s2[k+1]==s2[p])
                k++;
            l[p]=k;
        }
    k=-1;
    for(int t=0;t<n1;t++)
    {
        while(k>=0&&s1[t]!=s2[k+1])
            k=l[k];
        if(s1[t]==s2[k+1])
            k++;
        if(k+1==n2)
            {
                rez[++nr]=t-k;
                k=l[k];
            }
    }
    fout<<nr<<'\n';
    if(nr<=1000)
    for(i=1;i<=nr;++i)
        fout<<rez[i]<<" ";

    else
         for(i=1;i<=1000;++i)
        fout<<rez[i]<<" ";

}
    return 0;
}