Cod sursa(job #507952)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 7 decembrie 2010 09:21:31
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,q;
	l[1]=0;
	for (q=2; q<=m; q++) {
		k=l[q-1];
		while (k>0 && p[k+1]!=p[q])
			k=l[k];
		if (p[k+1]==p[q])
			k=k+1;
		l[q]=k;
	}
}

void kmp() {
	int k,t;
	k=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=k+1;
		if (k==m) {
			nr++;
			sol[nr]=t-m;
			k=l[k];
		}
	}
}
			


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;
}