Cod sursa(job #1918573)

Utilizator RG1999one shot RG1999 Data 9 martie 2017 16:01:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;
#define b1 83
#define b2 73
#define mod1 12345
#define mod2 10017
int ans[10001],cnt,i,n1,n2,hsh1,hsh2,ch1,ch2,p1,p2,ok;
char s1[2000001],s2[2000001];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(s1);
    gets(s2);
    n1=strlen(s1)-1;
    n2=strlen(s2)-1;
    p1=p2=1;
    for(i=0;i<=n1;i++)
    {
         if(i!=0)
        {
        p1=(p1*b1)%mod1;
        p2=(p2*b2)%mod2;
        }
        hsh1=(hsh1*b1+(s1[i]-'0'))%mod1;
        hsh2=(hsh2*b2+(s1[i]-'0'))%mod2;
    }
    for(i=0;i<=n1;i++)
        if(i<=n1)
    {
        ch1=(ch1*b1+(s2[i]-'0'))%mod1;
        ch2=(ch2*b2+(s2[i]-'0'))%mod2;
    }
    for(i=n1+1;i<=n2;i++)
    {
        if(ch1==hsh1&&ch2==hsh2)
        {
            if(cnt+1<=1000)
            ans[++cnt]=i-n1-1;
           else
            cnt++;
        }
        ch1=(b1*(ch1-((s2[i-n1-1]-'0')*p1)%mod1+mod1)+(s2[i]-'0'))%mod1;
        ch2=(b2*(ch2-((s2[i-n1-1]-'0')*p2)%mod2+mod2)+(s2[i]-'0'))%mod2;

    }
     if(ch1==hsh1&&ch2==hsh2)
        {
            if(cnt+1<=1000)
            ans[++cnt]=i-n1-1;
           else
            cnt++;
        }
    printf("%d\n",cnt);
    for(i=1;i<=min(cnt,1000);i++)
        printf("%d ",ans[i]);
    return 0;
}