# Given n strings, how to output their order after k phases of the radix sort (huge constraints)?

Disclaimer

This is not from an ongoing contest, this is from my course of ITMO on edx.org, which is a paid code so I cannot give you a direct link to the course.

Problem

You are given $$\displaystyle n$$ strings. Output their order after $$\displaystyle k$$ phases of the radix sort.

Input

The first line of the input file contains three integer numbers: $$\displaystyle n$$ , the number of strings, $$\displaystyle m$$, the length of each string, and $$\displaystyle k$$, the number of phases of the radix sort , , . $$(\displaystyle 1 <= n <= 10^{6}, 1 <= k <= m <= 10^{6}, n * m <= 5 * 10^{7})$$ Then the description of the strings follows. The format is not trivial. The i-string ($$\displaystyle 1 <= i <= n$$) is written as the i-th symbols of the second, …, ($$\displaystyle m + 1$$)-th lines of the input file. In simple words, the strings are written vertically. This is made intentionally to reduce the running time of your programs. If you construct the strings from the input lines in your program, you are doing the wrong thing.

The strings consist of small Latin letters, from "a" to "z" inclusively. In the ASCII table, all these letters go in a row in the alphabetic order. The ASCII code of "a" is 97, of "z" is 122.

Output

Print the indices of the strings in the order these strings appear after $$\displaystyle k$$ phases of the radix sort.

Example:

input
3 3 1
bab
bba
baa
output
2 3 1


In all examples the following strings are given:

• "bbb", with index 1;
• "aba", with index 2;
• "baa", with index 3.

Consider the first example. The first phase of the radix sort will sort the strings using their last symbol. As a result, the first string will be "aba" (index 2), then "baa" (index 3), then "bbb" (index 1). The answer is thus "2 3 1".

Other example:

input
3 3 2
bab
bba
baa
output
3 2 1

input
3 3 3
bab
bba
baa
2 3 1


One way to go for this problem might be sorting first k characters of each strings, this can be done using hashing + binary search but the languages that I know (Java, C++, Python) don't support hashing substring quickly.

Another way might be using a Trie, after $$\displaystyle k$$ phases of radix sort, it might equal with traversing the Trie in lexicographical order for nodes with depth $$\displaystyle k$$.

Because the constraints is huge and these methods are both error-prone. Running k steps of radix sort is not also an option because of the huge constraints. I really need help on this problem.

• “Running $k$ steps of radix sort is not also an option because of the huge constraints”. I doubt that. Since $n * m <= 5 * 10^{7}$, it is feasible to run $k$ steps of radix sort. – John L. Apr 30 '19 at 23:46
• It is strings with $10^{6}$ chars, and there are also $10^{6}$ strings, first step we compare the last char, second step we compare the next to last char and so on, please correct me if I'm wrong. – Loc Truong May 1 '19 at 6:05
• $10^6 * 10^6 > 5 * 10^7.$ – John L. May 1 '19 at 11:20
• you mean we can just radix sort these strings until k steps? I'm afraid it's not fast enough as suggested in the problem description. – Loc Truong May 1 '19 at 11:45
• The problem description suggests exactly that it is enough to just radix sort these strings. – John L. May 1 '19 at 15:26