Cod sursa(job #1140653)

Utilizator iarbaCrestez Paul iarba Data 12 martie 2014 10:06:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000005],b[2000005];
int q,i,p[2000005],n,m,x[1001],k;
void pre()
{
	p[1]=0;
	for(i=2;i<=n;i++){
		while((q)&&(a[q]!=a[i-1])){q=p[q];}
		if(a[q]==a[i-1]){q++;}
		p[i]=q;
					 }
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(a,sizeof(a),stdin);
    fgets(b,sizeof(b),stdin);
	n=strlen(a);
	m=strlen(b);
	pre();
	for(i=1;i<=m;i++){
		while((q)&&(a[q]!=b[i-1])){q=p[q];}
		if(a[q]==b[i-1]){q++;}
		if(q==n-1){q=p[n-1];if(k<1000){x[++k]=i-n+1;}}
					 }
	printf("%d\n",k);
	for(i=1;i<=k;i++){printf("%d ",x[i]);}
return 0;
}