Cod sursa(job #1394853)

Utilizator andreiulianAndrei andreiulian Data 20 martie 2015 19:09:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
#include<cstring>
using namespace std;
char x[2000005],y[2000005];
int pi[2000005],s[2000005];
void prefix();
void kmp();
int lx,ly,sol[1005],u,R;
int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    in>>(x+1);
    in>>(y+1);
    lx=strlen(x+1);
    ly=strlen(y+1);
    if(lx>ly) {out<<"0\n"; return 0;}
    prefix();
    kmp();
    int i;
    for(i=1;i<=ly && u<1000;++i)
    {
        if(s[i]==lx)
        {
            ++R;
            sol[++u]=i-lx;
        }
    }
    out<<R<<'\n';
    for(i=1;i<=u;++i) out<<sol[i]<<' ';
    out<<'\n';
}
void kmp()
{
    int k=0,i;
    if(x[1]==y[1]) s[1]=1,k=1;
    for(i=2;i<=ly;++i)
    {
        while(x[k+1]!=y[i] && k>0)
        {
            k=pi[k];
        }
        if(x[k+1]==y[i])
        {
            k++;
        }
        s[i]=k;
    }
}
void prefix()
{
    int k=0,i;
    pi[1]=0;
    for(i=2;i<=lx;++i)
    {
        while(x[k+1]!=x[i] && k>0)
        {
            k=pi[k];
        }
        if(x[k+1]==x[i])
        {
            ++k;
        }
        pi[i]=k;
    }
}