Cod sursa(job #2540085)

Utilizator adiaioanaAdia R. adiaioana Data 6 februarie 2020 18:49:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 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;
bool mark[NMAX];
long long hashA1,hashA2,hashB1,hashB2, P1, P2;
int main()
{
    cin>>A;
    cin>>B;
    nA=strlen(A);
    nB=strlen(B);

    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;
    }
    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];
        hashB1%=MOD1;
        hashB2=((hashB2+MOD2-(B[j-nA]*P2)%MOD2)%MOD2)*P+B[j];
        hashB2%=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; ++i)
        if(mark[i])
            cout<<i<<' ', --nr;
    return 0;
}