Cod sursa(job #2025485)

Utilizator darkraven13Stefan Bereghici darkraven13 Data 22 septembrie 2017 19:05:43
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;

int hashFunction(string s){
    const long long MOD = (long long) 2e18;
    const long long BASE = 123;

    long long hashKey = 0;
    long long bFactor = BASE;

    for (int i = 0; i < (int) s.size(); ++i){
        long long aux = bFactor * (long long) s[i];
        if (aux > MOD) aux %= MOD;
        hashKey = hashKey + aux;
        if (hashKey > MOD) hashKey -= MOD;
        bFactor = (bFactor * BASE) % MOD;
    }
    return hashKey;
}

vector <int> stringMatching(string a, string b){
    vector <int> pos;
    long long bHash = hashFunction(b);
    for (int i = 0; i <= (int) a.size() - b.size(); ++i){
        if (hashFunction(a.substr(i, b.size())) == bHash){
            pos.push_back(i);
        }
    }
    return pos;
}

int main(){
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a, b;
    cin >> b >> a;
    vector <int> strMatch = stringMatching(a, b);
    cout << strMatch.size() << "\n";
    for (auto& item : strMatch){
        cout << item << " ";
    }
    return 0;
}