Useful hash string problem

cf_spb_15.cpp

// http://codeforces.com/gym/100126/attachments/download/1321/20122013-tryenirovka-spbgu-b-15-heshi-ru.pdf
// Problem A
#include <bits/stdc++.h>
using namespace std;
typedef long long int lint;
typedef long double ldouble;

const lint p = 307;
const lint M = lint(1e9) + 7;

vector<lint> mem_pow; // it makes sense to store only F(l) = (p^(M-2)*p^l)%M

vector<string> strs;
vector< vector<lint> > phashes;
void computePHash(int i) {
    phashes[i].resize(strs[i].length()+1, 0);
    lint p_cur = 1;
    for (int l = 1; l <= strs[i].length(); ++l) {
        phashes[i][l] = (phashes[i][l-1] + strs[i][l-1]*p_cur)%M;
        p_cur = (p_cur*p)%M;
    }
}

lint powmod(lint x, lint y) {
    if (y == 0)
        return 1;
    lint prev = powmod(x, y/2);
    return ((prev * prev)%M * (y%2 ? x : 1) )%M;
}
// returns hash for [l, r) substring
lint h(int i, int l, int r) {
    lint dif = (phashes[i][r] - phashes[i][l]);
    while (dif < 0)
        dif += M;
    lint res = (dif *mem_pow[l])%M;
    return res;
}

string check(int len) {
    // compute hashes for all substrings of length len
    // if some hashes values exist for all strings - means that exist substring
    // in all strings, return true
    // map: hash -> bit mask (known that K <= 10)
    // K*N complexity
    int mask = (1<<strs.size()) - 1;

    unordered_map< lint, int > hashes(strs.size());
    for (int i = 0; i < strs.size(); ++i) {
        for (int l = 0; l <= strs[i].length() - len; ++l) {
            lint curh = h(i, l, l + len);
            hashes[curh] |= 1<<i;
            if (hashes[curh] == mask)
                return strs[i].substr(l, len);
        }
    }
    //for (auto v : hashes)
    //    if (v.second == mask)
    //        return true;
    return "";
}   

string solve() { // KNLogN complexity
    auto minStrLen = 100000;
    for (auto& s : strs)
        minStrLen = min(minStrLen, (int)s.length());
    string candidate;
    int l = 0, r = minStrLen+1;
    while (l+1 < r) {
        int m  = l + (r-l)/2;
        candidate = check(m);
        if (candidate.length() != 0) {
            l = m;
        } else {
            r = m;
        }
    }
    return candidate;
}

int main(int, char**) {
    std::ios::sync_with_stdio(false);
    ifstream fin("substr.in");
    ofstream fout("substr.out");

    // fillin pow_mem
    mem_pow.resize(10001, 1);
    mem_pow[1] = powmod(p, M-2);
    for (int i = 2; i < 10001; ++i)
        mem_pow[i] = (mem_pow[i-1]*mem_pow[1])%M;    

    int K;
    fin >> K;
    strs.resize(K);
    phashes.resize(K);
    for (int i = 0; i < K; ++i) {
        fin >> strs[i];
        // 1. compute prefix hash
        computePHash(i);
    }
    // Doesn't work
    //cout << phashes[0][1] << " " << phashes[0][2] << endl;
    //cout << h(0,4,6) << " " << h(0, 0, 2) << endl;
    fout << solve() << endl;

    return 0;
}