Cod sursa(job #2025518)

Utilizator darkraven13Stefan Bereghici darkraven13 Data 22 septembrie 2017 19:47:04
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
const long long MOD = (long long) 2e18;
const long long BASE = 123;

long long fastExp(long long n, int exp){
    switch(exp){
        case 0  : return 1;
        default : return (exp % 2 == 0) ? fastExp((n * n) % MOD, exp >> 1) : (n * fastExp(n, --exp)) % MOD;
    }
}

int hashFunction(string s){
    long long hashKey = 0;

    for (int i = 0; i < (int) s.size(); ++i){
        hashKey = (hashKey + fastExp(BASE, s.size() - 1 - i) * (long long) s[i]) % MOD;
    }
    return hashKey;
}

vector <int> stringMatching(string a, string b){
    if (b.size() > a.size()){
        return {};
    }
    vector <int> pos;
    long long bHash = hashFunction(b);
    long long rollingHash = hashFunction(a.substr(0, b.size()));
    long long basePow = fastExp(BASE, b.size() - 1);

    for (int i = 0; i <= (int) a.size() - b.size(); ++i){
        if (rollingHash == bHash){
            pos.push_back(i);
        }
        rollingHash = rollingHash - (basePow * (long long) a[i]) % MOD;
        rollingHash += (rollingHash < 0) ? MOD : 0;
        rollingHash = (rollingHash * BASE) % MOD;
        rollingHash += (long long) a[i + b.size()];
    }
    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;
}