Cod sursa(job #508005)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 7 decembrie 2010 12:13:00
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int max=2000001;
char p[max],s[max];
int i,n,m,nr,sol[1001];
int l[max];


void prefix() {
	int k,i;
	l[1]=0;
	for (i=2; i<=m; i++) {
		k=l[i-1];
		while (k>0 && p[i]!=p[k+1])
			k=l[k];
		if (p[k+1]==p[i]) k++;
		l[i]=k;
	}
}

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