Cod sursa(job #2208197)

Utilizator Eduard24Eduard Scaueru Eduard24 Data 28 mai 2018 17:17:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int i,hashA1,hashA2,P1,P2,MOD1=100153,MOD2=100189,P=73,NA,NB,hashB1,hashB2,nr;
char A[2000005],B[2000005],sol[2000005];

int main()
{
    fin>>A;
    fin>>B;
    NA=strlen(A);
    NB=strlen(B);
    P1=1;P2=1;
    for(i=0;i<NA;i++)
    {
        hashA1=(hashA1*P+A[i])%MOD1;
        hashA2=(hashA2*P+A[i])%MOD2;
        if(i!=0)
        {
            P1=(P1*P)%MOD1;
            P2=(P2*P)%MOD2;
        }
    }
    if(NA>NB)
    {
        fout<<0<<"\n";
        return 0;
    }
    for(i=0;i<NA;i++)
    {
        hashB1=(hashB1*P+B[i])%MOD1;
        hashB2=(hashB2*P+B[i])%MOD2;
    }
    nr=0;
    if(hashB1==hashA1 && hashB2==hashA2)
    {
        sol[0]=1;
        nr++;
    }
    for(i=NA;i<NB;i++)
    {
        hashB1=((hashB1-(B[i-NA]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
        hashB2=((hashB2-(B[i-NA]*P2)%MOD2+MOD2)*P+B[i])%MOD2;
        if(hashB1==hashA1 && hashB2==hashA2)
        {
            sol[i-NA+1]=1;
            nr++;
        }
    }
    fout<<nr<<"\n";
    nr=0;
    for(i=0;i<NB && nr<1000;i++)
    {
        if(sol[i]==1)
        {
            nr++;
            fout<<i<<" ";
        }
    }
    fin.close();
    fout.close();
    return 0;
}