Cod sursa(job #3277800)

Utilizator Laura139Anghel Laura Laura139 Data 17 februarie 2025 13:47:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 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 codA1=0, codA2=0;
    int a=0;
    for(int i=n-1;i>=0;i--)
        a=a*10+(A[i]-'0');
    codA1=hash1(a);
    codA2=hash2(a);

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

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