Cod sursa(job #2243691)

Utilizator vladm98Munteanu Vlad vladm98 Data 21 septembrie 2018 10:49:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> ans;

const long long base = 73, mod1 = 666013, mod2 = 1000000007;

string word, text;

long long rid(long long baza, long long exp, long long mod){
    long long 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){
    long long pathash1 = 0, pathash2 = 0, txthash1 = 0, txthash2 = 0;
    for(long long 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;
    }
    long long 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(long long 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);
    long long len = min(1000, int(ans.size()));
    fout << ans.size() << "\n";
    for(long long i = 0; i < len; ++i)
        fout << ans[i] << " ";
    return 0;
}