Cod sursa(job #1252794)

Utilizator andreeainfo_dAndreea Dutulescu andreeainfo_d Data 31 octombrie 2014 11:57:33
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<cstdio>
#include<cstring>
int a[2000005],d[2000005],i,n,m,k,c,nr;
char x[2000005],y[2000005];
using namespace std;
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);
    k=0;
    a[1]=0;
    for(i=2;i<=n;i++)
    {
            while (k>0&&x[i]!=x[k+1])
            {
                k=a[k];
            }
            if (x[i]==x[k+1]) k=k+1;
            a[i]=k;
    }
    m=strlen(y+1);
    for(i=1;i<=m;i++)
    {
            while (k>0&&y[i]!=x[k+1])
            {
                k=a[k];
            }
            if (y[i]==x[k+1]) k=k+1;
            d[i]=k;
    }
    for (i=1;i<=m;i++)
    {
        if (d[i]==n) nr++;
    }
    printf("%d\n",nr);
    nr=0;
    for (i=1;i<=m;i++)
    {
        if (d[i]==n)
        {
            printf("%d ",i-n);
            nr++;
            if (nr==1000) break;
        }
    }
        return 0;
}