For two or more strings \(s_1, s_2, \dots, s_n\), suppose that any two different strings have the first \(k\) characters in common. Given such strings, how can we find \(\max_{i \neq j} \mathrm{LCP}(s_i, s_j)\) for all \(i\)?

If any of \(s_1, s_2, \dots, s_n\) has a length exactly \(k\), then the answer to it is obviously \(k\). Let us now assume that the lengths are all \((k+1)\) or greater.

Classify \(s_1, s_2, \dots, s_n\) by the \((k+1)\)-th character; it is divided into \(\sigma\) groups, where \(\sigma \, ( = 26)\) is the size of the alphabet. If a group has at most one string, the answer founds to be \(k\). If a group has two or more strings, any two different strings in the group have the first \((k+1)\) characters in common. Thus, the problem can be recursively solved against the strings in the group with \(k \leftarrow k+1\).

The desired value is the answer when \((s_1, s_2, \dots, s_n) \leftarrow (S_1, S_2, \dots, S_N), k \leftarrow 0\). The method above can be implemented as a recursive function to solve it in a total of \(O(\sigma (N + \sum |S_i|))\) time.

Sample code