Cod sursa(job #395673)

Utilizator GotenAmza Catalin Goten Data 13 februarie 2010 16:58:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>
#include<string.h>
int pre[2000100],c[1100];
char a[2000100],b[2000100];
int main()
{
	int A,B,i,k=-1,ok=1;
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s %s",a,b);
	A=strlen(a)-1;
	B=strlen(b)-1;
	pre[0]=-1;
	for(i=1;i<=A;i++)
	{
		while(k>=0&&a[k+1]!=a[i])
			k=pre[k];
		if(a[k+1]==a[i])
			k++;
		pre[i]=k;
	}
	k=-1;
	for(i=0;i<=B;i++)
	{
		while(k>=0&&a[k+1]!=b[i])
			k=pre[k];
		if(a[k+1]==b[i])
			k++;
		if(k==A)
		{
			if(ok)
				c[++c[0]]=i-A;
			else
				c[0]++;
			if(c[0]==1000)
				ok=0;
		}
	}
	printf("%d\n",c[0]);
	for(i=1;i<=c[0]&&i<=1000;i++)
		printf("%d ",c[i]);
	return 0;
}