Cod sursa(job #184170)

Utilizator mihai0110Bivol Mihai mihai0110 Data 23 aprilie 2008 11:38:42
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#include<string.h>
#define MAXN 2000001
int m,i,n,nrsol;
int p[MAXN],sol[1001];
char s1[MAXN],s2[MAXN];
void prefix()
{
	int k=0,i;
	for(i=2;i<=m;i++)
	{
		while(k>0&&s2[k+1]!=s2[i])
			k=p[k];
		if(s2[k+1]==s2[i])
			k++;
		p[i]=k;
	}
}
void kmp()
{
	int i,k=0;
	for(i=1;i<=n;i++)
	{
		while(k>0&&s2[k+1]!=s1[i])
			k=p[k];
		if(s2[k+1]==s1[i])
			k++;
		if(k==m)
		{
			nrsol++;
			if(nrsol<=100)
				sol[nrsol]=i-m;
			k=p[m];
		}
	}
}
int main(void)
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s%s",s2+1,s1+1);
	s1[0]=' ';
	s2[0]=' ';
	m=strlen(s2);
	m--;
	n=strlen(s1);
	n--;
	prefix();kmp();
	printf("%d\n",nrsol);
	for(i=1;i<=nrsol&&i<=1000;i++)
		printf("%d ",sol[i]);
	return 0;
}