Cod sursa(job #3277787)

Utilizator Laura139Anghel Laura Laura139 Data 17 februarie 2025 13:31:06
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 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];

int hash1(int x)
{
    int galeata=0;
    int put=1;
    while(x!=0)
    {
        galeata=(galeata+((x%10)*put)%MOD1)%MOD1;
        x/=10;
        put*=BAZA1;
    }
    return galeata;
}

int hash2(int x)
{
    int galeata=0;
    int put=1;
    while(x!=0)
    {
        galeata=(galeata+((x%10)*put)%MOD2)%MOD2;
        x/=10;
        put*=BAZA2;
    }
    return galeata;
}

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

    int codA=0;
    int a=0;
    for(int i=n-1;i>=0;i--)
        a=a*10+(A[i]-'0');
    codA=hash2(hash1(a));

    int nrrasp=0;
    int codB=0;
    int nrB=0;
    for(int i=n-1;i>=0;i--)
        nrB=nrB*10+(B[i]-'0');
    codB=hash2(hash1(nrB));
    if(codB==codA)
    {
            nrrasp++;
            rasp[nrrasp]=0;
    }
    int p=pow(10, n);
    for(int i=n;i<m;i++)
    {
        nrB=nrB*10+(B[i]-'0');
        nrB=nrB%10;
        codB=hash2(hash1(nrB));
        if(codB==codA)
        {
            nrrasp++;
            rasp[nrrasp]=i-(n-1);
        }
    }

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