Cod sursa(job #342307)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 21 august 2009 12:08:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#include<string.h>
int n,m,nr;
int sol[1<<10],p[1<<21];
char v[1<<21],s[1<<21];

void prefix()
{
	int i,q=0;
	p[1]=0;
	for(i=2;i<=n;i++)
	{
		while(q && v[q+1]!=v[i])
			q=p[q];
		if(v[q+1]==v[i])
			q++;
		p[i]=q;
	}
}

void kmp()
{
	int i,q=0;
	for(i=1;i<=m;i++)
	{
		while(q && v[q+1]!=s[i])
			q=p[q];
		if(v[q+1]==s[i])
			q++;
		if(q==n)
		{
			q=p[q];
			nr++;
			if(nr<=1000)
				sol[nr]=i-n;
		}
	}
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	gets(v+1);n=strlen(v+1);
	gets(s+1);m=strlen(s+1);
	prefix();
	kmp();
	printf("%d\n",nr);
	int i;
	if(nr>1000)
		nr=1000;
	for(i=1;i<=nr;i++)
		printf("%d ",sol[i]);
	return 0;
}