Cod sursa(job #1252792)

Utilizator zikade9Irimia Rares zikade9 Data 31 octombrie 2014 11:52:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<cstdio>
#include<string.h>
int nr,i,n,m,k,h,p[2000009],d[2000009];
char x[2000009],y[2000009];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(x+1);
    n=strlen(x+1);
    gets(y+1);
    m=strlen(y+1);
    k=0;
    p[1]=0;
    for(i=2;i<=n;i++)
    {
        while(k>0&&x[i]!=x[k+1])
                k=p[k];
        if(x[i]==x[k+1]) k++;
        p[i]=k;
    }
    k=0;
    for(i=1;i<=m;i++)
    {
        while(k>0&&y[i]!=x[k+1])
                k=p[k];
        if(y[i]==x[k+1]) k++;
        d[i]=k;
    }
    for(i=1;i<=m;i++)
    {
        if(d[i]==n) nr++;
    }
    printf("%d\n",nr);
    for(i=1;i<=m;i++)
    {
        if(d[i]==n)
        {
            h++;
            printf("%d ",i-n);
            if(h==1000) break;
        }
    }
    return 0;
}