Cod sursa(job #153852)

Utilizator maria_pparcalabescu maria daniela maria_p Data 10 martie 2008 19:32:45
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<cstdio>
#include<cstring>

const long MAX=2000100;

long pi[MAX],nr,n,m,i,rez[1010];
char s[MAX],s1[MAX];

void prefix(){
	long k,i;
//	n=strlen(s1);
	k=0;pi[1]=0;
	for(i=2;i<n;i++){
		while(k>0 && s1[k+1]!=s1[i])
			k=pi[k];
		if(s1[k+1]==s1[i])
			k++;
		pi[i]=k;
	}
}

void kmp(){
	long k,i;
//	n=strlen(s1);m=strlen(s);
	k=0;
	for(i=1;i<m;i++){
		while(k>0 && s1[k+1]!=s[i])
			k=pi[k];
		if(s1[k+1]==s[i])
			k++;
		if(k==n-1){
			if(nr<1000)
				rez[nr++]=i-n+2;
			else
				nr++;
			k=pi[n-1];
		}
	}
}
int main(){
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(s1+1,MAX,stdin);
	fgets(s+1,MAX,stdin);
	n=1;m=1;
	for(;s[m]>='a' && s[m]<='z' || s[m]>='A' && s[m]<='Z' || s[m]>='0' && s[m]<='9';m++);
	for(;s1[n]>='a' && s1[n]<='z' || s1[n]>='A' && s1[n]<='Z' || s1[n]>='0' && s1[n]<='9';n++);
	/*for(i=1;i<n;i++)
		printf("%c",s1[i]);
	printf("\n");
	for(i=1;i<m;i++)
		printf("%c",s[i]);*/
	nr=0;
	prefix();
	kmp();
	printf("%ld\n",nr);
	for(i=0;i<nr && i<1000;i++)
		printf("%ld ",rez[i]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}