Analysis: Auto-Complete by Johnny Ho

To more easily find the k-th lexicographically smallest word that matches the prefix, we first sort the dictionary. From here, the straightforward solution is to take each prefix, go through the sorted sequence until we find k matches, and then print out the original position of the k-th matching word. This requires usage of a struct such as "pair" to remember the original position. This runs in worst-case O(N * L * W) time, where L is the length of each prefix.

To make this faster, note that we only need to find the first word that matches the prefix. Then the K-th word after that in the sorted sequence should be the answer, if it matches. To quickly find the first word that matches the prefix, we can use binary search on the sorted dictionary. This reduces the running time to O(N * L * log(W)). The full solution below uses C++'s convenient "lower_bound" function, though binary search can also be implemented as:

int lo = 0, hi = n;
while (lo + 1 < hi) {
	int mid = (lo + hi - 1) / 2;
	if (dict[mid].first < pref) {
		lo = mid + 1;
	} else {
		hi = mid + 1;
	}
}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<pair<string, int> > dict;

bool match(string& pref, string& word) {
	if (pref.size() > word.size()) return false;
	return word.substr(0, pref.size()) == pref;
}

int main() {
	freopen("auto.in", "r", stdin);
	freopen("auto.out", "w", stdout);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		dict.push_back(make_pair(s, i));
	}
	sort(dict.begin(), dict.end());
	for (int i = 0; i < m; i++) {
		int k;
		string pref;
		cin >> k >> pref;
		k--;
		int pos = lower_bound(dict.begin(), dict.end(), make_pair(pref, 0)) - dict.begin();
		// Ignore whether pos even matches at all
		int poss = pos + k;
		if (poss < dict.size() && match(pref, dict[poss].first)) {
			cout << dict[poss].second + 1 << '\n';
		} else {
			cout << -1 << '\n';
		}
	}
}