Cod sursa(job #1527853)

Utilizator Eugen_VlasieFMI Vlasie Eugen Eugen_Vlasie Data 18 noiembrie 2015 19:50:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long h1,h2,i,j,n,m,rest=1,p2571,p2572,hash1,nr,hash2,mod1=100003,mod2=100019;
char a[2000010],b[2000010];
queue<int> Q;
void ridput(int exp,int md)
{
    while(exp>1)
    {
        if(exp%2==0)
        {
            nr=(nr*nr)%md;
            exp/=2;
        }
        else
        {
            exp--;
            rest=(rest*nr)%md;
        }
    }
    nr=(nr*rest)%md;
}
int main()
{
    f>>a>>b;
    n=strlen(a);
    m=strlen(b);
    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;
        if(h1==hash1&&h2==hash2)
            Q.push(0);
    }
    nr=257;
    rest=1;
    ridput(n,mod1);
    rest=1;
    p2571=nr;
    nr=257;
    ridput(n,mod2);
    p2572=nr;
    for(i=n;i<m;i++)
    {
        h1=(h1*257+b[i])%mod1;
        h1=(h1-(b[i-n]*p2571)%mod1+mod1)%mod1;
        h2=(h2*257+b[i])%mod2;
        h2=(h2-(b[i-n]*p2572)%mod2+mod2)%mod2;
        if(h1==hash1&&h2==hash2)
        {
            Q.push(i-n+1);
        }
    }
    g<<Q.size()<<'\n';
    i=1;
    while(i<=1000&&!Q.empty())
    {
        g<<Q.front()<<" ";
        Q.pop();
        i++;
    }
    g<<'\n';
    return 0;
}