Cod sursa(job #2695797)

Utilizator adiaioanaAdia R. adiaioana Data 14 ianuarie 2021 15:53:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <cstring>
#include <vector>
#define MAX 2000001
#define MOD1 100007
#define MOD2 100021
#define P 73
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[MAX+10], B[MAX+10];
int nA,nB,P1,P2,hashA1,hashA2,hashB1,hashB2, pM1,pM2;
vector <int> match;
int main()
{
    cin.getline(A,MAX);
    cin.getline(B,MAX);
    nA=strlen(A);
    nB=strlen(B);
    if(nA>nB){
        cout<<0<<'\n';
        return 0;
    }

    P1=P2=1;
    for(int i=0; i<nA; ++i)
    {
        hashA1=(hashA1*P+A[i])%MOD1;
        hashA2=(hashA2*P+A[i])%MOD2;

        hashB1=(hashB1*P+B[i])%MOD1;
        hashB2=(hashB2*P+B[i])%MOD2;

        if(i>0)
        {
            P1=(P1*P)%MOD1;
            P2=(P2*P)%MOD2;
        }
    }
    if(hashA1==hashB1 && hashA2==hashB2)
        match.push_back(0);
    for(int i=nA; i<nB; ++i)
    {
        hashB1=((hashB1+MOD1-(P1*B[i-nA])%MOD1)*P+B[i])%MOD1;
        hashB2=((hashB2+MOD2-(P2*B[i-nA])%MOD2)*P+B[i])%MOD2;
        if(hashA1==hashB1 && hashB2==hashA2)
            match.push_back(i-nA+1);
    }

    cout<<match.size()<<'\n';
    for(auto it:match)
        cout<<it<<' ';
    return 0;
}