Cod sursa(job #2631758)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 30 iunie 2020 21:12:08
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <string>
#include <vector>
#include <list>

using namespace std;

const int MAX_NO_POS = 1000;
const int BASE = 62;
const int MOD = 10007;

void rabinKarp(string & A, string & B, int & n, list<int> & ans) {
    if (A.size() > B.size()) {
        return;
    }

    int hashWindow = 0;
    int hashPattern = 0;
    int pow = 1;
    for (int i = 0; i < A.size() - 1; i++) {
        pow = (pow * BASE) % MOD;
    }
    for (int i = 0; i < A.size(); i++) {
        hashWindow = (BASE * hashWindow + B[i]) % MOD;
        hashPattern = (BASE * hashPattern + A[i]) % MOD;
    }
    if (hashWindow == hashPattern && A == B.substr(0, A.size())) {
        n++;
        ans.push_back(0);
    }

    for (int i = A.size(); i < B.size(); i++) {
        hashWindow = (BASE * (hashWindow - (pow * B[i - A.size()])) + B[i]) % MOD;
        hashWindow += (hashWindow < 0) ? MOD : 0;
        if (hashWindow == hashPattern && A == B.substr(i - A.size() + 1, A.size())) {
            n++;
            if (n <= MAX_NO_POS) {
                ans.push_back(i - A.size() + 1);
            }
        }
    }
}

int main() {
    ifstream fin;
    ofstream fout;
    string A, B;

    fin.open("strmatch.in");
    fin >> A >> B;
    fin.close();

    int n = 0;
    list<int> ans;
    rabinKarp(A, B, n, ans);

    fout.open("strmatch.out");
    fout << n << endl;
    for (auto it = ans.begin(); it != ans.end(); ++it) {
        fout << *it << " ";
    }
    fout.close();

    ans.clear();

    return 0;
}