\(2\) 個以上の文字列 \(s_1, s_2, \dots, s_n\) について、どの異なる \(2\) つの文字列も先頭から \(k\) 文字以上一致しているとします。これらが入力として与えられたときに \(\max_{i \neq j} \mathrm{LCP}(s_i, s_j)\) を全ての \(i\) について求める方法を説明します。

\(s_1, s_2, \dots, s_n\) のうち長さがちょうど \(k\) のものがあるならば、それらに対する答えは明らかに \(k\) です。以下では全て長さが \(k+1\) 以上であるとします。

\(s_1, s_2, \dots, s_n\) を \(k+1\) 文字目によって分類します。文字の種類数を \(\sigma \, ( = 26)\) として、\(\sigma\) 個のグループに分類することができます。\(1\) 個以下の文字列しか存在しないグループについては、答えが \(k\) で確定します。一方で、\(2\) 個以上の文字列が存在するグループについては、同じグループ内のどの異なる \(2\) の文字列も先頭から \(k+1\) 文字以上が一致しています。よって、グループ内の文字列に対し、\(k \leftarrow k+1\) として再帰的に同じ問題を解けばよいです。

\((s_1, s_2, \dots, s_n) \leftarrow (S_1, S_2, \dots, S_N), k \leftarrow 0\) とした場合の答えが求めたい値です。上記の方法を再帰関数などで実装することにより、\(O(\sigma (N + \sum |S_i|))\) でこの問題を解くことができます。

実装例 (C++)