Cod sursa(job #3279828)

Utilizator Laura139Anghel Laura Laura139 Data 24 februarie 2025 15:48:22
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

const int BAZA1=67;
const int BAZA2=73;
const int MOD1=999983;
const int MOD2=999979;

int rasp[2000005];

long long hash1(string s)
{
    long long galeata=0;
    long long put=1;
    for(int i=0;i<s.size();i++)
    {
         galeata=(galeata+(((s[i]-'0')%10)*put)%MOD1)%MOD1;
         put=(put*BAZA1)%MOD1;
    }
    return galeata;
}

long long hash2(string s)
{
    long long galeata=0;
    long long put=1;
    for(int i=0;i<s.size();i++)
    {
         galeata=(galeata+(((s[i]-'0')%10)*put)%MOD2)%MOD2;
         put=(put*BAZA2)%MOD2;
    }
    return galeata;
}

int main()
{
    string A,B;
    cin>>A>>B;
    int n=A.size(), m=B.size();

    int codA1=0, codA2=0;
    codA1=hash1(A);
    codA2=hash2(A);

    int nrrasp=0;
    int codB1=0, codB2=0;
    for(int i=0;i+n-1<m;i++)
    {
        codB1=hash1(B.substr(i, n));
        codB2=hash2(B.substr(i,n));
        if(codB1==codA1 && codB2==codA2)
        {
            nrrasp++;
            rasp[nrrasp]=i;
        }
    }

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