Cod sursa(job #3333261)

Utilizator abetAlbert Voiculescu abet Data 12 ianuarie 2026 17:20:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.52 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 = 131;
    const int base2 = 137;

    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) {
        if (c >= '0' && c <= '9') return c - '0' + 1;
        if (c >= 'A' && c <= 'Z') return c - 'A' + 11;
        if (c >= 'a' && c <= 'z') return c - 'a' + 37;
        return 0;
    }

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<<" ";
    }
    return 0;
}