Cod sursa(job #3333847)

Utilizator Lex._.Lex Guiman Lex._. Data 15 ianuarie 2026 11:18:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define NMAX 2000000
#define P 73
using namespace std;

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

const int MOD[3]={1000000007, 1000000009, 666013};
int p[3]={1, 1, 1};
int hash_a[3], hash_b[3];

bitset<NMAX+1> potrivire;

int main()
{
    string a, b;
    in >> a >> b;
    for(int i=0; i<a.size(); i++)
    {
        for(int j=0; j<3; j++)
        {
            hash_a[j]=(1ll*hash_a[j]*P + a[i])%MOD[j];
            if(i>0) p[j]=(1ll*p[j]*P)%MOD[j];
        }
    }
    int nr_potriviri=0;
    for(int i=0; i<b.size(); i++)
    {
        for(int j=0; j<3; j++)
        {
            if(i>=a.size())
                hash_b[j]=((hash_b[j] - (1ll*b[i-a.size()]*p[j])%MOD[j] + MOD[j])*P + b[i])%MOD[j];
            else
                hash_b[j]=(1ll*hash_b[j]*P + b[i])%MOD[j];
        }
        if(i>=a.size()-1)
        {
            potrivire[i-a.size()+1]=(hash_a[0]==hash_b[0] && hash_a[1]==hash_b[1] && hash_a[2]==hash_b[2]);
            if(potrivire[i-a.size()+1]==1) nr_potriviri++;
        }
    }
    out << nr_potriviri << "\n";
    nr_potriviri=0;
    for(int i=0; i<b.size(); i++)
    {
        if(potrivire[i]==1)
        {
            out << i << " ";
            nr_potriviri++;
        }
        if(nr_potriviri==1000) break;
    }

    return 0;
}