\(S\) を \(S_1,S_2,\dots S_N\) を #(英小文字より辞書順で小さい文字列なら何でも良い) で連結した文字列の Suffix Array、LCP Array を求めます。

次に、 \(S_1,S_2, \dots, S_N\) に対して、部分文字列の取り方全て(開始位置と終端位置の取り方全て)を考えて、そこから重複を除くことを考えます。各接尾辞に対して、それと同じ開始位置の部分文字列の取り方について考えます。

ある接尾辞が \(S_i\) 由来の場合、 \(S_i\) 由来以外の接尾辞に対するLCPの最大値が \(L\) とすると、終端位置は長さが \(L + 1\) 以上になるように取れば \(S_i\) 以外の部分文字列になりません。

また、同じ文字列の部分文字列での重複を考慮するために、同じ部分文字列がある場合は、SA上で後に現れるものをカウントすることにします。SA上で一つ後ろの同じ文字列由来の接尾辞とのlcpを \(R\) とすると、終端位置は長さが \(R + 1\) 以上になるように取れば後でカウントする部分文字列になりません。

ある接尾辞に対応する、数えるべき部分文字列の個数は、(接尾辞の長さ)\({} - \max(L,R)\)

\(S_1,S_2,\dots, S_N\) の各接尾辞について、上記のものを足し合わせればよいです。

\(M=\sum_{i=1}^{N}|S_i|\) として、 \(L,R\) を適切に前計算すると、 \(O(M)\) 時間で計算できます。

Suffix Array、LCP Array の構築も含めて全体で \(O(M)\) で計算できます。

実装例(C++)