Cod sursa(job #2025552)

Utilizator darkraven13Stefan Bereghici darkraven13 Data 22 septembrie 2017 20:37:19
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
const long long MOD = (long long) 2e9;
const long long BASE = 255;

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);
    }
}

long long hashFunction(string s){
    long long hashKey = 0;
    long long baseFact = 1;

    for (int i = s.size() - 1; i >= 0; --i){
        hashKey = (hashKey + (baseFact * (long long) s[i]) % MOD) % MOD;
        baseFact = (baseFact * BASE) % 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);
        }
        if (i != (int) (a.size() - b.size())){
            rollingHash -= ((long long) a[i] * basePow) % MOD;
            rollingHash += (rollingHash < 0) ? MOD * (-rollingHash / MOD + 1) : 0;
            rollingHash = (rollingHash * BASE) % MOD;
            rollingHash = (rollingHash + (long long) a[i + b.size()]) % MOD;
        }
        if (rollingHash < 0 ){
            cout << rollingHash <<"\n";
        }
    }
    return pos;
}

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