Long Continuous Substrings

ランに含まれる部分文字列

与えられる情報の「 $S$ の $i$ 文字目を $A_i$ 回加えた」部分を ラン と呼ぶことにします。

$T$ の異なる空でない部分文字列のうち、 $1$ つのランに含まれるものは容易に数えられます。というのは、各文字についてその文字のランの最大長を求め、それらを足し合わせます。

よって、以下では $2$ つ以上のランにわたるもののみ数え上げます。

より単純な問題

まず、長さ $n$ の一般の文字列 $s$ が与えられる場合を考えます。

部分文字列を「接尾辞の接頭辞」と言い換えます。接尾辞を適当な順番に見て、その接頭辞のうち初めて現れるものの個数を数え上げます。これは文字列 $s$ の suffix array および LCP array を求めておくことで高速に実行できます。

ランレングス圧縮したまま suffix array + LCP array

$1 \leq s \leq N-1$ について、ラン $s+1$ 以降を連結した文字列を $\text{suf} _ s$ とします。また、 $\text{suf} _ s$ の先頭にラン $s$ の文字を $1$ つ追加した文字列を $\text{csuf} _ s$ とします。

$\text{csuf} _ s$ $(1 \leq s \leq N-1)$ を高速に辞書順に並べられるでしょうか？可能です。次の列 $B$ の suffix array を求めればよいです。

• $S_{N+1}$ は与えられるどの文字よりも辞書順で小さい文字 $\epsilon$ とする。
• $B_i=(S _ i,S _ {i+1},S _ {i+2},A _ {i+1})$
• $B$ の要素どうしを辞書順で比較するときは、 $(S _ i \times 1) + (S _ {i+1} \times A _ {i+1}) + (S _ {i+2} \times 1)$ を(暗に)辞書順で比較する。（ここでは $x \times y$ は文字 $x$ を $y$ 個並べた文字列、 $x+y$ は文字列の連結）

この suffix array から求めた LCP array を用いて $\text{csuf} _ s$ どうしの LCP も高速に求まります。

LCP array によって問題を言い換え

より単純な問題 と同様の問題に変換します。

$1 \leq s \leq N-1$ について、 $\sigma _ s$ を $T$ の部分文字列のうち、先頭の文字が $s$ 番目のランに属し、末尾の文字が $s$ 番目のランに属さないように取り出せるものの集合とします。 $\sigma _ s$ の要素のうち、ラン $s$ に含まれる部分の長さが $x$ 、それ以外の部分の長さが $y$ であるものを $\sigma _ s[(x,y)]$ と表します。

$\text{csuf} _ s$ の辞書順に $\sigma _ s$ を見ていき、 $\sigma _ s$ の要素のうちこれまでに現れたものの個数を数え上げたいです。 $\sigma _ l[(x,y)]$ と $\sigma _ r[(x,y)]$ が一致する $(x,y)$ の条件は以下です。

• $x \leq A _ l$
• $x \leq A _ r$
• $w$ を $\text{csuf} _ l$ と $\text{csuf} _ r$ の LCP とすると、 $y \leq w-1$

よって、この個数は、いくつかの長方形 $(x \leq a , y \leq b)$ の併合の面積で表せます。この長方形を $b$ が単調非減少かつ $a$ を単調非増加に並べたものを管理してクエリを処理すれば計算できそうです。

これを解く

suffix array の順番に $r$ を動かすと、 LCP が区間最小値クエリであることから「 $b$ が単調非減少」は suffix array 上の順序と同じになります。実際、必要な更新は管理する列の末尾にしかないので、長方形は stack で管理すればよく、計算量も $O(N)$ になります。

以上、 suffix array の構築以外 $O(N)$ 時間です。 suffix array の構築は $O(N \log^2 N)$ 時間または、基数ソートを用いることで $O(N \log N)$ 時間とできます。