Cod sursa(job #723354)

Utilizator The_DisturbedBungiu Alexandru The_Disturbed Data 25 martie 2012 13:16:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <string.h>
char a[2000013],b[2000013];
int na,nb,i,j,k,p[2000013],sol[1001];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
	gets(a);
	gets(b);
    na=strlen(a);
    nb=strlen(b);
    k=-1;
    p[0]=-1;
    for(i=1;i<na;i++)
	{
        while(k>-1&&a[i]!=a[k+1])k=p[k];
        if(a[i]==a[k+1])++k;
        p[i]=k; 
	}
	k=-1;
	j=0;
    for(i=0;i<nb;i++)
	{
        while(k>-1&&b[i]!=a[k+1])k=p[k];
        if(b[i]==a[k+1])k++;
        if(k==na-1)
		{
			if(j<1000)sol[j]=i-na+1;
			++j;
			k=p[k];
		}
	}
	printf("%d\n",j);
	if(j>1000)j=1000;
	for(i=0;i<j;++i)printf("%d ",sol[i]);
	return 0;
}