ABC 213 F — Common Prefixes

考察

接尾辞を辞書順に並べると、二つの接尾辞の共通接頭辞長は、その間にある隣接接尾辞どうしの一致長の最小値になる。求めたいのは個々の対の一致長ではなく総和なので、同じ最小値を持つ区間をまとめ、左右から単調スタックで集計する。

接尾辞対を隣接 LCP の区間へ写す

各接尾辞について、すべての接尾辞との最長共通接頭辞(LCP)の長さを足したい。長さは最大 N=106N=10^6 なので、全接尾辞対を列挙する二乗時間は避ける必要がある。多数の接尾辞の一致を扱うため、まず辞書順に並べて隣同士の関係に注目する。

以下、文字位置と配列の添字はすべて0始まりとし、S[a:]S[a:] を位置 aa から末尾までの接尾辞とする。空接尾辞は含めない。接尾辞配列 SA[r]SA[r] は辞書順で順位 rr の接尾辞の開始位置であり、0≤r<N0\leq r<N である。隣接 LCP 配列は

LCP[r]=lcp(S[SA[r]:],S[SA[r+1]:])(0≤r<N−1)LCP[r]=\mathrm{lcp}(S[SA[r]:],S[SA[r+1]:]) \qquad(0\leq r<N-1)

と定める。ここで lcp\mathrm{lcp} は二文字列の共通接頭辞長を表す。順位 p<qp<q の接尾辞の一致長は

lcp(S[SA[p]:],S[SA[q]:])=min⁡p≤k<qLCP[k]\mathrm{lcp}(S[SA[p]:],S[SA[q]:]) =\min_{p\leq k<q}LCP[k]

となる。同じ接頭辞を持つ接尾辞が辞書順で連続するためである。例えば両端が先頭から3文字一致するなら、その間の接尾辞もすべて同じ3文字で始まる。

この式を使って区間最小値の問い合わせ(RMQ)を高速にしても、接尾辞対そのものが二乗個ある。そこで、固定した順位 rr より左の相手からの寄与を L[r]L[r]、右からの寄与を R[r]R[r] とし、総和を直接求める。

L[r]=∑p=0r−1min⁡p≤k<rLCP[k]L[r]=\sum_{p=0}^{r-1}\min_{p\leq k<r}LCP[k]
R[r]=∑q=r+1N−1min⁡r≤k<qLCP[k]R[r]=\sum_{q=r+1}^{N-1}\min_{r\leq k<q}LCP[k]

相手がいない端では L[0]=R[N−1]=0L[0]=R[N-1]=0 とする。左寄与は「同じ右端までの全区間の最小値和」、右寄与はその左右を反転したものになった。

区間の最小値を始点群ごとにまとめる

LCP 列を左から読み、一つ前の終端までの各区間を新しい値 xx まで延ばす。最小値が vv だった区間の最小値は min⁡(v,x)\min(v,x) に変わり、新しく始まる長さ1の区間の最小値は xx となる。

従って、各始点を個別に更新せず、現在の終端に対して同じ最小値を持つ始点群をまとめればよい。スタックには組 (value,count)(\mathrm{value},\mathrm{count}) を値の昇順に持つ。個数は、その最小値を持つ区間の始点数である。さらに、その時点の全区間の最小値和を変数 sum に保持する。

初期状態は空スタック・sum = 0 とし、新値 xx を取り込む処理を次のようにする。これは擬似コードであり、stack と sum は呼出し間で保持する。

take(x):
    c = 1
    while stack が空でなく、末尾の value >= x:
        (v, count) = stack.pop()
        sum -= v * count
        c += count
    stack.push((x, c))
    sum += x * c
    return sum

最初の c=1c=1 は新しい長さ1の区間を表す。末尾の値 v≥xv\geq x のグループは、区間を延ばすとすべて最小値が xx になる。古い寄与 v×countv\times\mathrm{count} を引き、その始点数を cc へ移す。最後に新しい寄与 x×cx\times c を足せば、併合した区間を一つずつ更新したのと同じになる。v<xv<x のグループは最小値が変わらず、そのまま残してよい。

値が昇順なので、取り除くグループは末尾に連続する。等しい値も併合することで、残る値は狭義の昇順になる。例えばスタックが (2,1)(2,1) のときに x=2x=2 を取り込むと、既存の1区間と新しい1区間を (2,2)(2,2) にまとめ、総和は 2+2=42+2=4 になる。値が等しくても区間の個数は失ってはいけない。

左右の走査と元位置への復元

左寄与では、順位 r−1r-1 までの状態に LCP[r−1]LCP[r-1] を取り込むと、各区間が順位 rr まで延びる。右寄与では降順に走査し、順位 r+1r+1 までの状態に LCP[r]LCP[r] を取り込む。右走査のスタックの個数は、反転した LCP 列における始点数、すなわち元の順位で見た右側の相手の数を表す。

全体の手順は次の擬似コードになる。左右の走査で同じ take を使うが、状態は必ず初期化し直す。

L, R を長さ N の配列として、全要素を 0 にする
stack = 空, sum = 0
for r = 1, 2, ..., N-1:
    L[r] = take(LCP[r-1])

stack = 空, sum = 0
for r = N-2, N-3, ..., 0:
    R[r] = take(LCP[r])

for r = 0, 1, ..., N-1:
    ans[SA[r]] = L[r] + R[r] + (N - SA[r])
ans[0], ans[1], ..., ans[N-1] をこの順に出力する

自己との LCP は接尾辞の全長 N−SA[r]N-SA[r] であり、左右の走査に含まれないので別に足す。最後に接尾辞配列の順位ではなく、元の開始位置へ答えを戻す。出力の i+1i+1 行目が、0始まりの位置 ii の答えである。

ababa の左右の寄与を追う

独自例 S=ababaS=\texttt{ababa} では、接尾辞は辞書順で a, aba, ababa, ba, baba となる。従って

SA=(4,2,0,3,1),LCP=(1,3,0,2)SA=(4,2,0,3,1),\qquad LCP=(1,3,0,2)

である。表のスタックは底から末尾の順に書き、sum は取り込み後の値を示す。

走査・順位 rr取り込む xxスタック (value,count)(\mathrm{value},\mathrm{count})sum
左・11(1,1)1
左・23(1,1), (3,1)4
左・30(0,3)0
左・42(0,3), (2,1)2
右・32(2,1)2
右・20(0,2)0
右・13(0,2), (3,1)3
右・01(0,2), (1,2)2

左走査で r=3r=3 に進むときは x=0x=0 なので、(3,1)(3,1) と (1,1)(1,1) を両方 pop する。古い総和4から 3×13\times1 と 1×11\times1 を引き、個数を c=1+1+1=3c=1+1+1=3 にまとめる。新しい寄与は 0×30\times3 であり、左側3接尾辞との LCP がすべて0になる。値0のグループも始点数を保持する。

右走査の最後では、x=1x=1 に対して (3,1)(3,1) だけを pop し、(0,2)(0,2) は残る。新しい1区間と併合して (1,2)(1,2) を作るので、総和は 3−3×1+1×2=23-3\times1+1\times2=2 になる。

左右と自己の寄与を合わせると、次のようになる。

順位 rr開始位置 SA[r]SA[r]左 L[r]L[r]右 R[r]R[r]自己長 N−SA[r]N-SA[r]答え
040213
121337
204059
330224
412046

順位順の答え (3,7,9,4,6)(3,7,9,4,6) を開始位置へ戻すと、出力は (9,6,7,4,3)(9,6,7,4,3) となる。例えば先頭の ababa と元の位置順の各接尾辞との LCP は (5,0,3,0,1)(5,0,3,0,1) であり、総和9と一致する。

典型の発動条件

接尾辞配列と LCP 配列

発動条件: 多数の接尾辞どうしの辞書順関係や共通接頭辞長をまとめて扱うとき。

各接尾辞を順位へ変換し、二順位間の LCP を隣接 LCP 列の区間最小値として表す。

単調スタックによる区間最小値和

発動条件: 終端を順に延ばし、各終端について全始点からの区間最小値の総和を求めるとき。

延長による変更が v←min⁡(v,x)v\leftarrow\min(v,x) なので、新値以上のグループを一括で併合できる。値と担当する始点数を持ち、古い寄与を引いて新しい寄与を足す。左右を反転すれば、始点を固定した総和も同様に求められる。

問題固有の要素

固定した接尾辞自身との LCP はその接尾辞の長さであり、左右の LCP 配列から得る他接尾辞の寄与とは別に足す必要がある。

別の問題へ持ち帰る視点: 全要素との対比較和を左右走査へ分解したときは、比較対象が自分自身である対角成分が走査に含まれるかを確認する。

正当性

順位 p<qp<q の両端の接尾辞が先頭から hh 文字一致すれば、その接頭辞を持つ接尾辞は辞書順で連続するので、区間内の全接尾辞も同じ hh 文字を持つ。逆に、区間内の全隣接対が先頭から hh 文字一致すれば、両端も hh 文字一致する。従って両端の LCP は、その間の隣接 LCP の最小値に等しい。

スタックについて、処理済み列の現在の終端を持つ全非空区間の始点が、最小値ごとのグループに重複なく分けられ、sum が各グループの値と個数の積の総和になっていることを不変条件とする。空の状態では区間が存在せず、総和0で成り立つ。

新値 xx で延ばすと、既存区間のうち最小値 v<xv<x のものは変化せず、v≥xv\geq x のものは最小値が xx になる。後者はスタックの末尾部分に一致する。それらの古い寄与を引き、始点数を新しい長さ1の区間の1個と合わせて cc とし、寄与 x×cx\times c を加えるので、不変条件が保たれる。等しい値を pop しても、その個数を移すため漏れや重複は生じない。

左走査の順位 rr では、LCP[r−1]LCP[r-1] の取り込み後の区間と左側の各相手 p<rp<r が一対一に対応するので、sum は L[r]L[r] に等しい。右走査も逆順の列について同様に R[r]R[r] を得る。相手を左・右・自己に分けると全接尾辞を一度ずつ数えるため、自己長 N−SA[r]N-SA[r] を加え、開始位置 SA[r]SA[r] へ保存した値が求める答えである。

実装上の注意

  • LL と RR は全要素0で初期化し、L[0]L[0] と R[N−1]R[N-1] は更新しない。N=1N=1 では LCP 配列は空で両走査も空となり、自己長1だけを出力する。
  • 左走査は LCP[r−1]LCP[r-1]、右走査は LCP[r]LCP[r] を取り込み、その後の総和を保存する。右走査の前にスタックと sum を空・0へ戻す。
  • pop 条件は両方向とも v≥xv\geq x とする。等しい値をまとめても個数を捨てず、x=0x=0 でも同じ更新を行う。
  • sum・答え・値と個数の積には64 bit整数を使い、乗算前に型を広げる。すべて同じ文字の列では先頭の答えだけでも N(N+1)/2N(N+1)/2 に達し、32 bitに収まらない。
  • 接尾辞配列の順位のまま出力せず、ans[SA[r]] へ保存する。使うライブラリについても空接尾辞の有無と LCP の添字規約を確認する。

復習の核

  • 対ごとの値を高速に求めても、対の数が二乗なら足りない。要求が総和なら、同じ値になる相手をまとめられないか考える。
  • 単調スタックは「区間の最小値を担当する始点群」を持つ。新値で担当が変わる群の古い寄与を引き、個数を引き継いで新しい寄与を足す。
  • 左右へ分解した集計では、境界をまたぐ LCP の添字と、自己成分が含まれるかを確認する。順位から元位置へ戻すところまでが解法である。

計算量と制約

時間

英小文字の有界な文字種に対して SA-IS で接尾辞配列を構築すれば O(N)O(N)。隣接 LCP 構築も O(N)O(N) である。各走査では新値一つにつきグループを一度 push し、そのグループを pop するのは高々一度なので、while 文の総反復数は O(N)O(N)。左右の走査・答えの復元・出力を含め、全体で O(N)O(N) となる。比較ソートを各段で使う倍増法なら接尾辞配列構築が O(Nlog⁡2N)O(N\log^2 N) となり、それが全体の時間計算量になる。

空間

入力文字列、接尾辞配列・逆順位・LCP、左右の寄与・スタック・答えを保持して O(N)O(N)。スタックのグループ数も高々 N−1N-1 である。

制約との対応

公式制約は 1≤N≤1061\leq N\leq10^6、英小文字からなる長さ NN の文字列で、制限時間3秒・メモリ1024 MiB。SA-IS と線形 LCP 構築を用い、二乗個の接尾辞対や区間を実際には列挙しない。一つの答えの上界は全接尾辞長の和 N(N+1)/2N(N+1)/2 で、最大 500000500000500000500000 となるため64 bit整数が必要である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Common Prefixes の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 接尾辞の順序とLCPを索引化する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 接尾辞順序・LCP索引

    補助タグ: 単調stack・queueによる支配候補の削除

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 接尾辞の順序とLCPを索引化する

    • 接尾辞の辞書順とLCPを索引化し、出現範囲・部分文字列順位・distinct数・巡回shiftを処理できる。

    先に読む単元:

    この解説で扱わないこと:

    • rolling hashによる一致比較と回文半径。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題