Cod sursa(job #184191)

Utilizator mihai0110Bivol Mihai mihai0110 Data 23 aprilie 2008 11:58:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#include<string.h>
#define MAXN 2000005
int m,i,n,nrsol;
int p[MAXN],sol[1001];
char s1[MAXN],s2[MAXN];
void prefix(void)
{
	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(void)
{
	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<=1000)
				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);
	s2[0]=' ';
	s1[0]=' ';
	m=strlen(s2)-1;
	n=strlen(s1)-1;
	prefix();kmp();
	printf("%d\n",nrsol);
	for(i=1;i<=nrsol&&i<=1000;i++)
		printf("%d ",sol[i]);
	return 0;
}