Cod sursa(job #305082)

Utilizator TyberFMI Dogan Adrian Ioan Lucian Tyber Data 16 aprilie 2009 10:39:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#define nmax 2000001
char a[nmax],b[nmax];
void pref();
void kmp();
int min(int,int);
int n,m,p1[nmax],p2[1001],n1;
int main(){
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(a,sizeof(a),stdin);
	fgets(b,sizeof(b),stdin);
	while((a[m]>='A'&&a[m]<='Z')||(a[m]>='a'&&a[m]<='z')||(a[m]>='0'&&a[m]<='9'))m++;
	while((b[n]>='A'&&b[n]<='Z')||(b[n]>='a'&&b[n]<='z')||(b[n]>='0'&&b[n]<='9'))n++;
	for(int i=m;i!=0;i--){
		a[i]=a[i-1];
		a[0]=' ';
	}
	for(int i=n;i!=0;i--){
		b[i]=b[i-1];
		b[0]=' ';
	}
	pref();
	kmp();
	printf("%d\n",n1);
	for(int i=1;i<=min(n1,1000);i++)
		printf("%d ",p2[i]);
	printf("\n");
	return 0;
}
void pref(){
	int i,c=0;
	for(i=2,p1[1]=0;i<=m;i++){
		while(c&&a[c+1]!=a[i])
			c=p1[c];
		if(a[c+1]==a[i])
			c++;
		p1[i]=c;
	}
}
void kmp(){
	int i,c=0;
	for(i=1;i<=n;i++){
		while(c&&a[c+1]!=b[i])
			c=p1[c];
		if(a[c+1]==b[i])
			c++;
		if(c==m){
			c=p1[m];
			n1++;
			if(n1<=1000)
				p2[n1]=i-m;
		}
	}
}
int min(int a,int b){
	if(a<b)return a;
	else return b;
}