Cod sursa(job #3305812)

Utilizator alexbaldovin20alex baldovin alexbaldovin20 Data 5 august 2025 12:59:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021

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

char A[MAXN], B[MAXN];
int NA,NB,hashA1, hashA2, P1, P2;
char match[MAXN];
int main() {
    in>>A>>B;
    NA=strlen(A);
    NB=strlen(B);
    P1=P2=1;
    hashA1=hashA2=0;
    for (int i=0;i<NA;i++) {
        hashA1=(hashA1*P+A[i])%MOD1;
        hashA2 =(hashA2*P+A[i])%MOD2;
        if (i!=0) {
            P1=(P1*P)%MOD1,
            P2=(P2*P)%MOD2;
        }
    }
    if (NA>NB)
    {
        out<<"0";
        return 0;
    }
    int hash1=0,hash2=0;
    for (int i=0;i<NA;i++) {
        hash1=(hash1*P+B[i])%MOD1,
           hash2=(hash2*P+B[i])%MOD2;
    }

    int Nr=0;
    if (hash1==hashA1 and hash2==hashA2)
        match[0]=1,Nr++;
    for (int i=NA;i<NB;i++)
    {
        hash1=((hash1-(B[i-NA]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
        hash2=((hash2-(B[i-NA]*P2)%MOD2+MOD2)*P+B[i])%MOD2;
        if (hash1==hashA1 && hash2==hashA2)
            match[i-NA+1]=1,Nr++;
    }
    out<<Nr<<'\n';
    Nr=0;
    for (int i = 0; i < NB && Nr < 1000; i++)
        if (match[i]) {
            Nr++,
            out<<i<<" ";
        }
    return 0;
}