Cod sursa(job #3334653)

Utilizator Vlad3218Garcea Vlad Vlad3218 Data 18 ianuarie 2026 20:36:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <cstring>
#include <vector>
#include <fstream>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int N;
vector <int> ans;
const int Base = 63;
const int MOD1 = 1e9+7;
const int MOD2 = 1e9+9;
char A[2000001],B[2000001];
long long hashA1,hashA2;
long long hashB1,hashB2;
long long P1=1,P2=1;
void Citire(){
    fin>>A>>B;
}
bool Verificare(int st,int dr){
    for (int i=st;i<=dr;++i)
        if (A[i-st]!=B[i])
            return false;
    return true;
}
void Rezolvare(){
    int nA=strlen(A),nB=strlen(B);
    if (nA>nB)
        return;
    P1=1,P2=1;
    for (int i=0;i<nA;++i){
        hashA1=(hashA1*Base+A[i])%MOD1;
        hashA2=(hashA2*Base+A[i])%MOD2;
        if (i!=0){
            P1=(P1*Base)%MOD1;
            P2=(P2*Base)%MOD2;
        }
    }
    for (int i=0;i<nA;++i){
        hashB1=(hashB1*Base+B[i])%MOD1;
        hashB2=(hashB2*Base+B[i])%MOD2;
    }
    if (hashA1==hashB1 && hashA2==hashB2)
        if (Verificare(0,nA-1)){
            N++;
            ans.push_back(0);
        }
    for (int i=nA;i<nB;++i){
        hashB1=(((hashB1-B[i-nA]*P1)%MOD1+MOD1)*Base+B[i])%MOD1;
        hashB2=(((hashB2-B[i-nA]*P2)%MOD2+MOD2)*Base+B[i])%MOD2;
        if (hashA1==hashB1 && hashA2==hashB2)
            if (Verificare(i-nA+1,i)){
                N++;
                if (N<1000)
                    ans.push_back(i-nA+1);
            }
    }
}
void Afisare(){
    fout<<N<<"\n";
    for (auto i:ans)
        fout<<i<<' ';
}
int main()
{
    Citire();
    Rezolvare();
    Afisare();
    return 0;
}