Cod sursa(job #3240496)

Utilizator pregoliStana Andrei pregoli Data 16 august 2024 00:55:16
Problema Potrivirea sirurilor Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>
using namespace std;
const string FILE_NAME = "strmatch.";
ifstream fin(FILE_NAME + "in");
ofstream fout(FILE_NAME + "out");

#define CH2NR(ch) (ch - 'A' + 1)
constexpr int ALPHA_LEN = 'z' - 'a' + 1, MOD = 1e9 + 7;
vector<int> RK(const string &text, const string &pattern) {//Rabin-Karp
    const int txtSize = text.length(), pattSize = pattern.length();

    vector<int> alPow(max(txtSize, pattSize)); //pows of ALPHA_LEN
    alPow[0] = 1;
    for (size_t i = 1; i < alPow.size(); i++) {
        alPow[i] = (1LL * alPow[i - 1] * ALPHA_LEN) % MOD;
    }

    int pattHash = 0;
    for (int i = 0; i < pattSize; i++) {
        pattHash = (pattHash + 1LL * CH2NR(pattern[i]) * alPow[i]) % MOD;
    }

    vector<int> txtHashAt(txtSize + 1);//[i]->txt hash in interval [0, i)
    for (int i = 0; i < txtSize; i++) {
        txtHashAt[i + 1] = (txtHashAt[i] + 1LL * CH2NR(text[i]) * alPow[i]) % MOD;
    }

    vector<int> ans;
    for (int i = 0; i <= txtSize - pattSize; i++) {
        int currHash = (txtHashAt[i + pattSize] - txtHashAt[i] + MOD) % MOD;
        if (currHash == 1LL * pattHash * alPow[i] % MOD) {
            ans.push_back(i);
        }
    }
    return ans;
}

int main() {
    string text, pattern;
    getline(fin, pattern);
    getline(fin, text);

    vector<int> ans = RK(text, pattern);
    fout << ans.size() << endl;
    for (int it : ans) {
        fout << it << ' ';
    }
    fout << endl;
    fout.close();
    return 0;
}