Cod sursa(job #916309)

Utilizator deresurobertoFMI - Deresu Roberto deresuroberto Data 16 martie 2013 12:23:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<cstdio>
#include<cstring>
int n,m,i,k,nr,v[2000005],w[2000005];
char s[2000005],t[2000005];


void citire()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	gets(s+1);
	gets(t+1);
	n=strlen(s+1);
	m=strlen(t+1);
}

void prefix()
{
	k=0;
	for(i=2;i<=n;i++){
		while(k>0 && s[k+1]!=s[i])k=v[k];
		if(s[k+1]==s[i])k++;
		v[i]=k;
	}
}

void kmp()
{
	k=0;
	for(i=1;i<=m;i++){
		while(k>0 && s[k+1]!=t[i])k=v[k];
		if(s[k+1]==t[i])k++;
		if(k==n){
			nr++;
			w[nr]=i-n;
			k=v[k];
		}
	}
	
}

void afisare()
{
	printf("%d\n",nr);
	if(nr>1000)nr=1000;
	for(i=1;i<=nr;i++)printf("%d ",w[i]);
	
}

int main()
{
	citire();
	prefix();
	kmp();
	afisare();
	return 0;
}