Cod sursa(job #3333257)

Utilizator abetAlbert Voiculescu abet Data 12 ianuarie 2026 17:07:38
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
class RabinKarpHash {
private:
    const int mod = 1e9 + 7;
    const int base = 31;
    vector<int> hash;
    vector<int> power;


    int add(int a, int b) {
        a += b;
        if (a >= mod) a -= mod;
        return a;
    }


    int sub(int a, int b) {
        a -= b;
        if (a < 0) a += mod;
        return a;
    }

    int mul(int a, int b) {
        return (int)((1LL * a * b) % mod);
    }


    int charToInt(char c) {
        return c - 'A' + 1;
    }

public:

    RabinKarpHash(string &s) {
        int n = s.size();
        hash.resize(n);
        power.resize(n);

        hash[0] = charToInt(s[0]);
        power[0] = 1;

        for (int i = 1; i < n; ++i) {
            hash[i] = add(mul(hash[i - 1], base), charToInt(s[i]));
            power[i] = mul(power[i - 1], base);
        }
    }

    int getSubHash(int l, int r) {
        int h = hash[r];
        if (l > 0) {
            h = sub(h, mul(hash[l - 1], power[r - l + 1]));
        }
        return h;
    }
};


vector<int> searchPattern(string &text, string &pattern) {
    int n = text.size(), m = pattern.size();

    RabinKarpHash textHash(text);
    RabinKarpHash patHash(pattern);

    int patternHash = patHash.getSubHash(0, m - 1);
    vector<int> result;

    for (int i = 0; i <= n - m; i++) {
        int 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;
}