Cod sursa(job #2721979)

Utilizator adiaioanaAdia R. adiaioana Data 12 martie 2021 15:22:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <string>
#include <vector>
#define P 73
#define MOD1 100019
#define MOD2 100057
#define LL long long
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");


string A,B;
LL P1,P2,hashA1,hashA2,hashB1,hashB2;
vector <int> sol;

bool comp()
{
    return (hashA1==hashB1 && hashA2 ==hashB2);
}

int main()
{
    int i, Na,Nb;
    cin>>A>>B;
    P1=P2=1;
    Na=A.size();
    Nb=B.size();
    if(Na>Nb)
    {
        cout<<0<<'\n';
        return 0;
    }
    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;
        }
        hashB1=(hashB1*P+B[i])%MOD1;
        hashB2=(hashB2*P+B[i])%MOD2;
    }

    if(comp())
        sol.push_back(0);
    for(i=Na; i<Nb; ++i)
    {
        hashB1=(((hashB1+MOD1-(P1*B[i-Na])%MOD1)%MOD1)*P+B[i])%MOD1;
        hashB2=(((hashB2+MOD2-(P2*B[i-Na])%MOD2)%MOD2)*P+B[i])%MOD2;
        if(comp())
            sol.push_back(i-Na+1);
    }

    cout<<sol.size()<<'\n';
    for(i=0; i<min(1000,(int)sol.size()); ++i)
        cout<<sol[i]<<' ';
    cout<<'\n';
    return 0;
}