Cod sursa(job #2540100)

Utilizator adiaioanaAdia R. adiaioana Data 6 februarie 2020 19:00:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <cstring>
#define NMAX 2000010
#define MOD1 100007
#define MOD2 100021
#define P 73
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[NMAX], B[NMAX];
int nA, nB, mark[NMAX];
long long hashA1, hashA2, hashB1, hashB2, P1, P2;

void prehash();
int main()
{
    cin>>A;
    cin>>B;
    nA=strlen(A);
    nB=strlen(B);
    if(nA>nB)
    {
        cout<<0<<'\n';
        return 0;
    }
    prehash();

    mark[0]=(hashA1==hashB1 && hashA2==hashB2);
    int nr=0;
    nr+=mark[0];

    for(int j=nA; j<nB; ++j)
    {
        hashB1=(((( hashB1+ MOD1-(B[j-nA]*P1)%MOD1)%MOD1)*P)+B[j])%MOD1;
        hashB2=(((( hashB2+ MOD2-(B[j-nA]*P2)%MOD2)%MOD2)*P)+B[j])%MOD2;

        mark[j-nA+1]=( hashA1==hashB1 && hashA2==hashB2 );
        nr+=mark[j-nA+1];
    }
    cout<<nr<<'\n';
    for(int i=0; i<nB && nr>0; nr-=mark[i++])
        if(mark[i])
            cout<<i<<' ';
    return 0;
}

void prehash()
{
    hashA1=hashA2=0;
    P1=P2=1;
    for(int i=0; i<nA; ++i)
    {
        hashA1=(hashA1*P+A[i])%MOD1;
        hashA2=(hashA2*P+A[i])%MOD2;
        if(i<nA-1)
        {
            P1=P1*P, P1%=MOD1;
            P2=P2*P, P2%=MOD2;
        }
    }
    hashB1=hashB2=0;
    for(int i=0; i<nA; ++i)
    {
        hashB1=(hashB1*P+B[i])%MOD1;
        hashB2=(hashB2*P+B[i])%MOD2;
    }
}