Cod sursa(job #3333384)

Utilizator TzepuAndrei Tzepu Data 13 ianuarie 2026 10:51:15
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;

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

#define MOD 10000007

int h[2000001];

int pow (int a, int b){
    int rez=1;
    while (b){
        if (b%2==1){///e impar
            rez=1ll*a*rez%MOD;
        }
         a=1ll*a*a%MOD;
        b/=2;
    }
    return rez;
}

int main()
{
    int hashA=0,hashB=0,p1=1,p2=1,baza=37,inv;
    string a,b;
    vector<int> poz;
    in >> a >> b;
    inv=pow(baza,MOD-2);
    for (int i=0; i<a.size(); i++){
        hashA=(hashA+1ll*a[i]*p1)%MOD;
        p1=1ll*p1*baza%MOD;
    }
    for (int i=0; i<b.size(); i++){
        if (i<a.size()){
            hashB=(hashB+1ll*b[i]*p2)%MOD;
            p2=1ll*p2*baza%MOD;
        } else{
            hashB=1ll*(hashB-b[i-a.size()]+1ll*b[i]*p2+MOD)*inv%MOD;
        }
        if (hashA==hashB){
            poz.push_back(i-a.size()+1);
        }
    }
    out << poz.size() << '\n';
    for (int i=0; i<min(int(poz.size()),1000); i++){
        out << poz[i] << " ";
    }
    return 0;
}