Cod sursa(job #3333256)

Utilizator abetAlbert Voiculescu abet Data 12 ianuarie 2026 17:06:01
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.35 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
class RabinKarpDoubleHash{
private:
    const int mod1 = 1e9 + 7;
    const int mod2 = 1e9 + 9;
    const int base1 = 31;
    const int base2 = 37;
    vector<int> hash1, hash2;
    vector<int> power1, power2;
    int add(int a, int b, int mod){
        a += b;
        if (a >= mod) a -= mod;
        return a;
    }
    int sub(int a, int b, int mod){
        a -= b;
        if (a < 0) a += mod;
        return a;
    }
    int mul(int a, int b, int mod){
        return (int)(1LL * a * b % mod);
    }
    int charToInt(char c){
        return c - 'A' + 1;
    }
public:
    RabinKarpDoubleHash(const string &s){
        int n = s.size();
        hash1.resize(n);
        hash2.resize(n);
        power1.resize(n);
        power2.resize(n);
        hash1[0] = hash2[0] = charToInt(s[0]);
        power1[0] = power2[0] = 1;
        for (int i = 1; i < n; i++) {
            hash1[i] = add(mul(hash1[i - 1], base1, mod1), charToInt(s[i]), mod1);
            hash2[i] = add(mul(hash2[i - 1], base2, mod2), charToInt(s[i]), mod2);
            power1[i] = mul(power1[i - 1], base1, mod1);
            power2[i] = mul(power2[i - 1], base2, mod2);
        }
    }
    pair<int,int> getSubHash(int l, int r){
        int h1 = hash1[r];
        int h2 = hash2[r];
        if (l > 0) {
            h1 = sub(h1, mul(hash1[l - 1], power1[r - l + 1], mod1), mod1);
            h2 = sub(h2, mul(hash2[l - 1], power2[r - l + 1], mod2), mod2);
        }
        return {h1, h2};
    }
};
vector<int> searchPattern(string &text, string &pattern){
    int n = text.size();
    int m = pattern.size();
    if (m > n) return {};
    RabinKarpDoubleHash textHash(text);
    RabinKarpDoubleHash patHash(pattern);
    auto patternHash = patHash.getSubHash(0, m - 1);
    vector<int> result;
    for (int i = 0; i <= n - m; i++) {
        auto subHash = textHash.getSubHash(i, i + m - 1);
        if (subHash == patternHash) {
            result.push_back(i);
        }
    }
    return result;
}
int main() {
    string txt;
    string pat;
    in>>pat>>txt;
    vector<int> positions = searchPattern(txt, pat);
    out<<positions.size()<<'\n';
    for(int idx : positions){
        out<<idx<<" ";
    }
    out<<'\n';
    return 0;
}