Cod sursa(job #632560)

Utilizator geniucosOncescu Costin geniucos Data 11 noiembrie 2011 16:49:14
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<stdio.h>
#include<cstring>
using namespace std;
int m,i,j,nr,r1,r2,s11,s12,p11,p12,p1,p2,s1,s2,n,d[2000002];
char c1,a[2000002],b[2000002];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1);
m=strlen(a+1);
scanf("%c",&c1);
gets(b+1);
n=strlen(b+1);
s1=0;
s2=0;
p1=1;
p2=1;
for(i=m;i>=1;i--)
{
	s1=(s1+p1*a[i])%666013;
	if(i>1) p1=(p1*137)%666013;
	s2=(s2+p2*a[i])%10003;
	if(i>1) p2=(p2*139)%10003;
}
s11=0;
s12=0;
p11=1;
p12=1;
for(i=m;i>=1;i--)
{
	s11=(s11+p11*b[i])%666013;
	if(i>1) p11=(p11*137)%666013;
	s12=(s12+p12*b[i])%10003;
	if(i>1) p12=(p12*139)%10003;
}
r1=p11;
r2=p12;
nr=0;
if(s11==s1&&s12==s2) 
{
	nr++;
	d[nr]=1;
}
for(j=m+1;j<=n;j++)
{
	s11=(((s11-r1*b[j-m])%666013+666013)*137+b[j])%666013;
	s12=(((s12-r2*b[j-m])%10003+10003)*139+b[j])%10003;
	if(s11==s1&&s12==s2)
	{
		nr++;
		if(nr<=1000) d[nr]=j-m+1;
	}
}
printf("%d\n",nr);
if(nr>1000) nr=1000;
for(i=1;i<=nr;i++)
	printf("%d ",d[i]);
return 0;
}