Cod sursa(job #1258996)

Utilizator gabrieligabrieli gabrieli Data 9 noiembrie 2014 16:55:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <cstdint>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

constexpr uint64_t M1 = 15485863;
constexpr uint64_t M2 = 15485867;
constexpr uint64_t B = 128;

inline uint64_t hashf(const string& text, const uint64_t m) {
    uint64_t result = 0;
    for (char c : text)
        result = ((result * B) % m + c) % m;
    return result;
}
   
inline uint64_t rehash(
        uint64_t old_h,
        char c_significant, char c_new,
        const uint64_t rehash_base,
        const uint64_t m) {
    return ((old_h * B) % m + m - (c_significant * rehash_base) % m + c_new) % m;
}

inline uint64_t pow_mod(uint64_t base, uint64_t exp, uint64_t mod) {
    uint64_t result = 1;
    
    while (exp) {
        if (exp % 2)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    
    return result;
}

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    
    string query, text;
    fin >> query >> text;
    
    if (query.size() > text.size()) {
        fout << "0\n";
        return 0;
    }
    
    size_t matches = 0;
    size_t positions[1001];
    
    uint64_t HQ1 = hashf(query, M1);
    uint64_t HQ2 = hashf(query, M2);
    
    size_t i = 0;
    uint64_t h1 = hashf(text.substr(0, query.size()), M1),
             h2 = hashf(text.substr(0, query.size()), M2);
    uint64_t B1 = pow_mod(B, query.size(), M1),
             B2 = pow_mod(B, query.size(), M2);
    
    while (true) {
        if (h1 == HQ1 && h2 == HQ2) {
            matches++;
            if (matches <= 1000) positions[matches] = i;
        }
        
        if (i + query.size() < text.size()) {
            h1 = rehash(h1, text[i], text[i + query.size()], B1, M1);
            h2 = rehash(h2, text[i], text[i + query.size()], B2, M2);
            i++;
        }
        else break;
    }
     
    fout << matches << '\n';
    for (size_t i = 1; i <= 1000 && i <= matches; ++i) fout << positions[i] << ' ';
    fout << endl;
    
    return 0;
}