Cod sursa(job #1252783)

Utilizator binicBinica Nicolae binic Data 31 octombrie 2014 11:47:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,i,j,k,q,d[2000002],p[2000002];
char x[2000002],y[2000002];
void constructie_pi()
{
    int k,i;
    k=0;
    p[1]=0;
    for(i=2;i<=n;i++)
    {
        while(k>0&&x[k+1]!=x[i])
            k=p[k];
        if(x[i]==x[k+1])k++;
        p[i]=k;
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(x+1);
    gets(y+1);
    x[0]=' ';
    y[0]=' ';
    n=strlen(x)-1;
    m=strlen(y)-1;
    constructie_pi();
    k=0;
    for(i=1;i<=m;i++)
    {
        while(k>0&&x[k+1]!=y[i])
            k=p[k];
        if(y[i]==x[k+1])k++;
        d[i]=k;
    }
    for(i=1;i<=m;i++)
        if(d[i]==n)q++;
    printf("%d\n",q);
    q=0;
    for(i=n;i<=m;i++)
        if(d[i]==n)
        {
            printf("%d ",i-n);
            q++;
            if(q==1000)break;
        }
    return 0;
}