Cod sursa(job #369367)

Utilizator EugenStoicaEugen Stoica EugenStoica Data 28 noiembrie 2009 10:51:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<stdio.h>
#include<string.h>
#define NM 2000001

char s[NM],t[NM];
int ls,lt,u[NM],v[1001],nr;

void prefix()
{
int i,j;
u[0]=-1;
j=-1;
for(i=1;i<ls;i++)
	{
	while(j>-1&&s[i]!=s[j+1])j=u[j];
	if(s[i]==s[j+1])j++;
	u[i]=j;
	}
}

int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",s,t);
ls=strlen(s);
lt=strlen(t);
int i,j;
prefix();
j=-1;
for(i=0;i<lt;i++)
	{
	while(j>-1&&t[i]!=s[j+1])j=u[j];
	if(t[i]==s[j+1])j++;
	if(j==ls-1)
		{
		nr++;
		if(nr<=1000)v[nr]=i-ls+1;
		}
	}
printf("%d\n",nr);
if(nr>1000)nr=1000;
for(i=1;i<=nr;i++)printf("%d ",v[i]);
return 0;
}