solution for atcoder contest arc97, A

arc97_a.cpp

// Solution of https://arc097.contest.atcoder.jp/tasks/arc097_a
// using string hashing 
// Good as a source of code for general hashing with reversed element
// But overcomplicated for this problem -- it is possible to just generate all the 
// sustrings, sort/unique them and return k-th
//
#include <bits/stdc++.h>
using namespace std;
typedef long long int lint;

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

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

string str;
vector<lint> phashes;
void computePHash() {
    phashes.resize(str.length()+1, 0);
    lint p_cur = 1;
    for (int l = 1; l <= str.length(); ++l) {
        phashes[l] = (phashes[l-1] + str[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 l, int r) {
    lint dif = phashes[r] - phashes[l];
    while (dif < 0)
        dif += M;
    lint res = (dif *mem_pow[l])%M;
    return res;
}

int main(int, char**) {
    std::ios::sync_with_stdio(false);

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

    cin >> str;
    size_t K;
    cin >> K;
    // compute prefix hash
    computePHash();
    
    unordered_map<lint, pair<int, int> > s;
    for (int i = 0; i < str.length(); ++i) {
        for (int l = 1; l <= min(K, str.length() - i) ; ++l) {
            auto ch = h(i, i+l);
//cout << str.substr(i, l) << " " << ch << endl;
            s.emplace(ch, make_pair(i, l));     
        }
    }

    vector<string> ss;
    for (auto v = s.begin(); v != s.end(); ++v) {
        ss.push_back( str.substr(v->second.first, v->second.second));
    }
    sort(ss.begin(), ss.end());
    cout << ss[K-1] << endl;

    return 0;
}