文字列長の合計を \(L\) とします。

求めるものは、すべての文字列のペアについてのLCPの長さの総和なので、文字列を並び替えても答えは変わりません。そこで、文字列たちをソートします。Suffix Arrayを適切に用いることで \(O(L)\) 時間で行えます。（ソート関数などを用いて普通にソートしても \(O(L\log L)\) くらいになるような気がします）。indexを振り直すことで、\(S_i\) はソートされているとします。

\(A_i=f(S_i,S_{i+1})\) とし、すべての \(A_i\) を求めます。愚直に LCP を求めることで、全体で \(O(L)\) 時間で行えます。

\(f(S_i,S_j)=\min(f(S_i,S_{i+1}),f(S_{i+1},S_{i+2}),\ldots,f(S_{j-1},S_j))\) であることに注意すると、もとの問題は「\((A_1,\ldots,A_{N-1})\) の全ての非空連続部分列についてminを求め、その和を求めよ」という問題になります。

\(\sum_{i=1}^j\min(A_i,\ldots,A_j)\) を \(j=1,2,\ldots\) の順に考えます（＝数列の右端に \(1\) つずつ要素を追加して答えの増分を考えます）。
これは、ヒストグラムの最大長方形問題と同様に、スタックを用いて増加列を管理することで高速に計算できます。毎回スタックの中身をすべて確認することにしても、各時点のスタックサイズは \(A_j\) 以下であることから、全体で \(O(\sum A_i)\subset O(L)\) で処理ができます。

以上により全体で \(O(L)\) 時間でこの問題を解くことができました。