Cod sursa(job #169930)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 2 aprilie 2008 11:05:47
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#include <string.h>
#define N 2000005
char a[N],b[N],n,m;
int pi[N],v[1001];
void pii(){
	int k=0,i;
	pi[1]=0;
	for(i=2;i<=n;i++){
		while(k>0 && a[k+1]!=a[i])
			k=pi[k];
		if(a[k+1]==a[i])
			k++;
		pi[i]=k;
	}
}
void potrivire(){
	int i,q;
	q=0;
	for(i=1;i<=m;i++){
		while(q && a[q+1]!=b[i])
			q=pi[q];
		if(a[q+1]==b[i])
			q++;
		if(q==n)
			if(v[0]<1000) v[++v[0]]=i-n;
	}
}
int main(){
	
	int i;
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1);
	m=strlen(b+1);
	pii();
	potrivire();
	printf("%d\n",v[0]);
	for(i=1;i<=v[0];i++)
		printf("%d ",v[i]);
	return 0;
}