Cod sursa(job #2238799)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 7 septembrie 2018 17:17:44
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> ans;

const int base = 256, mod = 11;

string word, text;

int rid(int baza, int exp){
    int rez = 1;
    while(exp > 0){
        if(exp % 2){
            rez *= baza;
            rez %= mod;
        }
        baza *= baza;
        baza %= mod;
        exp /= 2;
    }
    return rez;
}

void RabinKarp(string pat, string txt){
    int pathash = 0, txthash = 0;
    for(int i = 0; i < int(pat.size()); ++i){
        pathash = (pathash * base + int(pat[i])) % mod;
        txthash = (txthash * base + int(txt[i])) % mod;
    }
    int pow = rid(base, int(pat.size()) - 1);
    for(int i = 0; i < int(txt.size()) - int(pat.size()); ++i){
        if(pathash == txthash){
            int ok = 1;
            for(int j = 0; j < int(pat.size()) && ok; ++j){
                if(pat[j] != txt[i + j])
                    ok = 0;
            }
            if(ok)
                ans.push_back(i);
        }
        if(i < int(txt.size()) - int(pat.size())){
            txthash = (base * (txthash - pow * int(txt[i])) + int(txt[i + int(pat.size())])) % mod;
            if(txthash < 0)
                txthash += mod;
        }
    }
}

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> word >> text;
    RabinKarp(word, text);
    int len = min(1000, int(ans.size()));
    fout << len << "\n";
    for(int i = 0; i < len; ++i)
        fout << ans[i] << " ";
    return 0;
}