Cod sursa(job #560127)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 18 martie 2011 12:39:08
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
#include <string.h>

#define max 2000001

int n,m,l[max],sol[1001],nr,k,i;
char p[max],t[max];

int main () {
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	fgets(p+1,max,stdin);
	fgets(t+1,max,stdin);
	
	n=strlen(p+1)-1;
	m=strlen(t+1)-1;
	l[1]=0;
	for (i=2; i<=n; i++) {
		k=l[i-1];
		while (k>0 && p[i]!=p[k+1]) k=l[k];
		if (p[i]==p[k+1]) k++;
		l[i]=k;
	}
	k=0; nr=0;
	for (i=1; i<=m; i++) {
		while (k>0 && t[i]!=p[k+1]) k=l[k];
		if (t[i]==p[k+1]) k++;
		if (k==n) {
			nr++;
			if (nr<=1000) sol[nr]=i-n;
			k=l[n];
		}
	}
	
	printf("%d\n",nr);
	if (nr>1000) nr=1000;
	
	for (i=1; i<nr; i++) printf("%d ",sol[i]);
	printf("%d\n",sol[nr]);
	return 0;
}