Cod sursa(job #1098924)

Utilizator binicBinica Nicolae binic Data 5 februarie 2014 12:33:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<cstdio>
#include<cstring>
using namespace std;
#define m1 100007
#define m2 100021
int n,m,i,a1,a2,k,p1,p2,b1,b2,c[2000001];
char a[2000001],b[2000001];
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	gets(a);
	gets(b);
	n=strlen(a)-1;
	m=strlen(b)-1;
	if(n>m)
    {
        printf("0");
        return 0;
    }
	for(i=0;i<=n;i++)
    {
        a1=(a1*73+a[i])%m1;
        a2=(a2*73+a[i])%m2;
    }
    p1=1;
    p2=1;
    for(i=0;i<=n;i++)
    {
        b1=(b1*73+b[i])%m1;
        b2=(b2*73+b[i])%m2;
        if(i>0)
        {
            p1=(p1*73)%m1;
            p2=(p2*73)%m2;
        }
    }
    if(a1==b1&&a2==b2)k++,c[k]=0;
    for(i=n+1;i<=m;i++)
    {
        b1=((b1-(b[i-n-1]*p1)%m1+m1)*73+b[i])%m1;
        b2=((b2-(b[i-n-1]*p2)%m2+m2)*73+b[i])%m2;
        if(a1==b1&&a2==b2)k++,c[k]=i-n;
    }
    printf("%d\n",k);
    if(k>1000)k=1000;
    for(i=1;i<=k;i++)
        printf("%d ",c[i]);
	return 0;
}