Cod sursa(job #1252786)

Utilizator zikade9Irimia Rares zikade9 Data 31 octombrie 2014 11:50:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<cstdio>
#include<string.h>
int nr,i,n,m,k,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)
        {
            printf("%d ",i-n);
        }
    }
    return 0;
}