Cod sursa(job #3279869)

Utilizator Laura139Anghel Laura Laura139 Data 24 februarie 2025 16:49:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int BAZA1=521;
const int BAZA2=523;
const int MOD1=666013;
const int MOD2=312013;

int rasp[1005];

long long hash_(string s, const int MOD, const int BAZA)
{
    long long galeata=0;
    for(int i=s.size()-1;i>=0;i--)
    {
         galeata=((galeata*BAZA)+s[i])%MOD;
    }
    return galeata;
}

int main()
{
    string A,B;
    cin>>A>>B;
    int n=A.size(), m=B.size();
    int p1=1, p2=1;
    for(int i=1;i<n;i++)
    {
        p1=(p1*MOD1)%BAZA1;
        p2=(p2*MOD2)%BAZA2;
    }

    int codA1=0, codA2=0;
    codA1=hash_(A, MOD1, BAZA1);
    codA2=hash_(A, MOD2, BAZA2);

    int nrrasp=0;
    long long codB1=0, codB2=0;
    codB1=hash_(B.substr(0, n), MOD1, BAZA1);
    codB2=hash_(B.substr(0, n), MOD2, BAZA2);
    for(int i=n;i<m;i++)
    {
        if(codB1==codA1 && codB2==codA2)
        {
            nrrasp++;
            if(nrrasp<=1000)
                rasp[nrrasp]=i;
        }
        codB1=(MOD1+codB1+((B[i-n]*p1)))%MOD1;
        codB1=(((codB1*BAZA1)%MOD1)+B[i])%MOD1;
        codB2=(MOD2+codB2+((B[i-n]*p2)))%MOD2;
        codB2=(((codB2*BAZA2)%MOD2)+B[i])%MOD2;
    }

    cout<<nrrasp<<'\n';
    for(int i=1;i<=min(nrrasp, 1000);i++)
        cout<<rasp[i]<<" ";
    return 0;
}