Cod sursa(job #184187)

Utilizator mihai0110Bivol Mihai mihai0110 Data 23 aprilie 2008 11:54:18
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 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()
{
	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);
	fgets(s2, sizeof(s2), stdin);
	fgets(s1, sizeof(s1), stdin);
	for (; (s1[n] >= 'A' && s1[n] <= 'Z') || (s1[n] >= 'a' && s1[n] <= 'z') 
			|| (s1[n] >= '0' && s1[n] <= '9'); ++n);
	for (; (s2[m] >= 'A' && s2[m] <= 'Z') || (s2[m] >= 'a' && s2[m] <= 'z')
			|| (s2[m] >= '0' && s2[m] <= '9'); ++m);
	for (i = m; i; --i) s2[i] = s2[i-1]; s2[0] = ' ';
	for (i = n; i; --i) s1[i] = s1[i-1]; s1[0] = ' ';	
	prefix();kmp();
	printf("%d\n",nrsol);
	for(i=1;i<=nrsol&&i<=1000;i++)
		printf("%d ",sol[i]);
	return 0;
}