Cod sursa(job #1278674)

Utilizator AndreiITCuriman Andrei AndreiIT Data 29 noiembrie 2014 10:46:11
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char A[2000012],B[2000012];
int mod1=299777,mod2=299771,ANS[2000012];
int main()
{
    fin>>A>>B;
    int lunga=strlen(A);
    int lungb=strlen(B);
    int hashA1=0;
    int hashA2=0;
    int putmax1=1;
    int putmax2=1;
    for(int i=0;i<lunga;i++)
    {
        hashA1=(hashA1*71+A[i])%mod1;
        hashA2=(hashA2*71+A[i])%mod2;
        if(i)
        {
            hashA1=(hashA1*71)%mod1;
            hashA2=(hashA2*71)%mod2;
        }
    }
    if(lunga>lungb)
    {
        fout<<"0";
        return 0;
    }
    int hashB1=0;
    int hashB2=0;
    for(int i=0;i<lunga;i++)
    {
        hashB1=(hashB1*71+B[i])%mod1;
        hashB2=(hashB2*71+B[i])%mod2;
    }
    int sol=0;
    if(hashA1==hashB1 and hashA2==hashB2)
    {
        ANS[0]=1;
        sol++;
    }
    //fout<<sol<<endl;
    //sol=1;
    for (int i=lunga;i<lungb;i++)
    {
        hashB1=((hashB1-(B[i-lunga]*putmax1)%mod1+mod1)*71+B[i])%mod1;
        hashB2=((hashB2-(B[i-lunga]*putmax2)%mod2+mod2)*71+B[i])%mod2;
        if(hashB1==hashA1 and hashB2==hashA2)
            ANS[i-lunga+1]=1,sol++;
    }
    fout<<sol<<endl;
    sol=0;
    for(int i=0;i<lungb and sol<1000;i++)
        if(ANS[i]!=0)
            sol++,
            fout<<i;
    fout<<endl;
    return 0;
}