Cod sursa(job #755428)

Utilizator Marius96Marius Gavrilescu Marius96 Data 5 iunie 2012 19:03:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<cstdio>
#include<cstring>
char a[2000005];
char b[2000005];
int  t[2000005];
int la;
int ans[1005];
int ansnr;

void mkt()
{
	int p=2;
	int c=0;
	t[0]=-1;
	t[1]=0;
	while(p<la){
		if(a[p-1]==a[c])
			c++,t[p]=c,p++;
		else if(c)
			c=t[c];
		else
			t[p]=0,p++;
	}
}

int main()
{
	freopen ("strmatch.in","r",stdin);
	freopen ("strmatch.out","w",stdout);
	gets (a);
	gets (b);
	int m=0,i=0,lb=strlen (b);
	la=strlen (a);
	mkt();
	while(m+i<lb){
		if(a[i]==b[m+i]){
			if(i==la-1){
				if(ansnr<1000)
					ans[ansnr++]=m+1;
				m+=i-t[i];
				i=-1;
			}
			i++;
		} else {
			m+=i-t[i];
			if(t[i]>-1)
				i=t[i];
			else
				i=0;
		}
	}
	printf ("%d\n",ansnr);
	if(ansnr>1000)
		ansnr=1000;
	for(int i=0;i<ansnr;i++)
		printf ("%d ",ans[i]);
	return 0;
}