Cod sursa(job #1538183)

Utilizator Eugen_VlasieFMI Vlasie Eugen Eugen_Vlasie Data 28 noiembrie 2015 17:02:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000010],b[2000010];
int i,j,hash1,hash2,p1=1,p2=1,h1,h2,n,m,mod1=100003,mod2=100069;
queue<int> Q;
int main()
{
    f>>a>>b;
    n=strlen(a)-1;
    m=strlen(b)-1;
    for(i=0;i<=n;i++)
    {
        hash1=(hash1*257+a[i])%mod1;
        hash2=(hash2*257+a[i])%mod2;
    }
    for(i=0;i<=n;i++)
    {
        h1=(h1*257+b[i])%mod1;
        h2=(h2*257+b[i])%mod2;
    }
    for(i=0;i<=n;i++)
    {
        p1=(p1*257)%mod1;
        p2=(p2*257)%mod2;
    }
    if(h1==hash1&&h2==hash2)
        Q.push(0);
    for(i=n+1;i<=m;i++)
    {
        h1=((h1*257+b[i]-b[i-(1+n)]*p1)%mod1+mod1)%mod1;
        h2=((h2*257+b[i]-b[i-(1+n)]*p2)%mod2+mod2)%mod2;
        if(h1==hash1&&h2==hash2)
            Q.push(i-n);
    }
    i=1;
    g<<Q.size()<<'\n';
    while(i<=1000&&!Q.empty())
    {
        i++;
        g<<Q.front()<<" ";
        Q.pop();
    }
    return 0;
}