Cod sursa(job #1984601)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 25 mai 2017 14:48:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

vector<int> RabinKarp(const string &s, const string &pattern)
{
    vector<int> ret;
    if(s.size() < pattern.size())
        return ret;
    const int base = 173;
    unsigned long long basePow = 1;
    unsigned long long patternHash = 0;
    unsigned long long sHash = 0;
    int i;
    for(i = 0; i < pattern.size(); ++i)
    {
        patternHash = patternHash * base + pattern[i];
        sHash = sHash * base + s[i];
    }
    for(int i = 1; i < pattern.size(); ++i)
        basePow *= base;
    if(patternHash == sHash)
        ret.push_back(0);
    int start, stop;
    while(i < s.size())
    {
        start = i - pattern.size() + 1;
        stop = i;
        sHash -= s[start - 1] * basePow;
        sHash = sHash * base + s[stop];

        if(sHash == patternHash)
            ret.push_back(start);
        ++i;
    }
    return ret;
}

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    string a, b;
    in >> a >> b;
    vector<int> sol = RabinKarp(b, a);
    out << sol.size() << "\n";
    for(auto x:sol)
        out << x << " ";
    in.close();
    out.close();
    return 0;
}