\(\text{LCP}(s,t)\lt \text{LCP}(s,u)\) を満たす相異なる文字列 \(s,t,u\) が、辞書順で \(s\lt t\lt u\) となることがあり得ないことは、 \((\text{LCP}(s,t)+1)\) 文字目を比較するときの結果で矛盾することからわかります。逆方向 \((u\lt t\lt s)\) も同様です。

よって、与えられた文字列を辞書順でソートしたあとに隣接する文字列の組の \(\text{LCP}\) のみ考えても十分です。

長さの合計が \(N\) であるような列たちのソートは \(O(N\log N)\) 時間でできて、必要な \(\text{LCP}\) の計算は \(O(N)\) 時間でできるので、全体で \(O(N\log N)\) 時間で問題に答えることができます。