Cod sursa(job #2243697)

Utilizator vladm98Munteanu Vlad vladm98 Data 21 septembrie 2018 11:00:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> ans;

const int base = 73, mod1 = 666013, mod2 = 7340033;

string word, text;

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

void RabinKarp(string pat, string txt){
    int  pathash1 = 0, pathash2 = 0, txthash1 = 0, txthash2 = 0;
    for(int i = 0; i < int(pat.size()); ++i){
        pathash1 = (base * pathash1 + int(pat[i])) % mod1;
        pathash2 = (base * pathash2 + int(pat[i])) % mod2;
        txthash1 = (base * txthash1 + int(txt[i])) % mod1;
        txthash2 = (base * txthash2 + int(txt[i])) % mod2;
    }
    int pow1 = rid(base, int(pat.size()) - 1, mod1), pow2 = rid(base, int(pat.size()) - 1, mod2);
    if(pathash1 == txthash1 && pathash2 == txthash2)
        ans.push_back(0);
    for(int i = int(pat.size()); i < int(txt.size()); ++i){
        txthash1 = ((txthash1 - (int(txt[i - int(pat.size())]) * pow1) % mod1 + mod1) * base + int(txt[i])) % mod1;
        txthash2 = ((txthash2 - (int(txt[i - int(pat.size())]) * pow2) % mod2 + mod2) * base + int(txt[i])) % mod2;
        if(pathash1 == txthash1 && pathash2 == txthash2)
            ans.push_back(i - int(pat.size()) + 1);
    }
}

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