Cod sursa(job #157559)

Utilizator razvi9Jurca Razvan razvi9 Data 13 martie 2008 09:26:59
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<cstdio>
#include<cstring>
using namespace std;
char a[2000001],b[2000001];
int n,m,i,j,k,pi[20000001],s[1001];
inline void kmp()
{
	n=strlen(a);
	k=-1;
	pi[0]=-1;
	for(i=1;i<n;i++){
		while(k>=0 && a[k+1]!=a[i])
			k=pi[k];
		if(a[k+1]==a[i])
			k++;
		pi[i]=k;}

	m=strlen(b);
	k=-1;
	for(i=0;i<m;i++){
		while(k>=0 && a[k+1]!=b[i])
			k=pi[k];
		if(a[k+1]==b[i]) k++;
		if(k==n-1) {
			s[0]++;
			if(s[0]<=1000) s[s[0]]=i-n+1;}}
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s %s",a,b);
	kmp();
	printf("%d\n",s[0]);
	for(i=1;i<=1000&&i<=s[0];i++)
		printf("%d ",s[i]);
	fclose(stdout);
	return 0;
}