Cod sursa(job #157582)

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

	m=strlen(b);
	k=0;
	for(i=1;i<=m;++i){
		while(k>0 && a[k]!=b[i-1])
			k=pi[k];
		if(a[k]==b[i-1]) k++;
		if(k==n) {
			s[0]++;
			if(s[0]<=1000) s[s[0]]=i-n;}}
}
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;
}