Cod sursa(job #1120267)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 24 februarie 2014 22:39:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int nmax = 2000005;
const int mod1 = 100009;
const int mod2 = 100003;
const int base = 107;
int n,m,i,q,sol[nmax],cnt,a1,a2,b1,b2,B1,B2;
char a[nmax],b[nmax];
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s",a+1); n=strlen(a+1);
	scanf("%s",b+1); m=strlen(b+1);
    for(i=1;i<=n;i++)
    {
        a1=(a1*base+a[i])%mod1;
        a2=(a2*base+a[i])%mod2;
    }
    B1=B2=1;
    for(i=1;i<n;i++)
    {
        B1=(B1*base)%mod1;
        B2=(B2*base)%mod2;
    }
    for(i=1;i<=n;i++)
    {
        b1=(b1*base+b[i])%mod1;
        b2=(b2*base+b[i])%mod2;
    }
    if(a1==b1 && a2==b2) sol[++cnt]=0;
    for(;i<=m;i++)
    {
        b1=((b1-(B1*b[i-n])%mod1+mod1)*base+b[i])%mod1;
        b2=((b2-(B2*b[i-n])%mod2+mod2)*base+b[i])%mod2;
        if(a1==b1 && a2==b2)
            if(++cnt<=1000) sol[cnt]=i-n;

    }
    printf("%d\n",cnt);
    for(i=1;i<=min(1000,cnt);i++) printf("%d ",sol[i]);
	return 0;
}