Cod sursa(job #2631862)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 1 iulie 2020 13:47:31
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <string>
#include <list>
 
using namespace std;
 
const int MAX_NO_POS = 1000;
const int BASE = 256;
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;
}