考察
LCP(S_i,S_j) は二文字列が共有する非空 prefix の個数に等しい。したがって各 prefix p について、それを持つ文字列 pair 数を足せば同じ答えになる。
全入力長が3×10^5なので、全 prefix を Trie の node として共有すれば、同じ文字列断片を重複保持せずに頻度を集計できる。
採用する候補: 文字列を順に Trie へ挿入し、各 prefix node を過去に通った文字列数を今回の寄与へ加える。
各 pair は共有する各 prefix node で一回ずつ数えられ、処理量は総文字数に比例する。
棄却する候補: 全文字列 pair ごとに先頭から一致長を比較する。
文字列が似ている最悪例で pair 数 N² と比較長が重なり、総入力長制約内でも二乗時間になる。
S_j の各 prefix node の count は、それを共有する i<j の本数なので、その総和が j と過去全文字列との LCP 合計になる。
文字列末端かどうかではなく、root 以外の通過 node すべてへ count を持つことで prefix 一個ごとの寄与を表す。
空 Trie を用意し、j=1..N の順に S_j の文字をたどる。各文字後の node で現在 count を答えへ加え、その後(または二段目の走査で)S_j が通る全 node の count を1増やす。
典型の発動条件
LCP の共通 prefix 数への分解
発動条件: 全 pair の longest common prefix 長総和を求めるとき。
長さを共有 prefix ごとの indicator sum に展開する。
Trie 上の通過頻度
発動条件: 多数文字列の prefix ごとの出現数を総入力長で集計したいとき。
prefix を node に共有し、挿入時に path count を更新する。
問題固有の要素
最大一致長という max 型量を「長さ k 以上である」の layer cake に分けると、prefix node ごとの単純な pair 数になる。
別の問題へ持ち帰る視点: 整数値の総和は threshold indicator の和へ展開すると、共有構造で数えやすくなる場合がある。
正当性
LCPは共有する非空prefix個数。各prefix nodeの通過文字列pair数を足す主客転倒が全LCP和と一致する。新文字列のnodeで既存countを先に足すとi<jのpairだけ各共有prefixで一回数え、その後countを増やして次入力へ備えられる。root空prefixは長さ0なので足さない。
実装上の注意
- count を加えてから今回文字列を登録し、自分自身との pair を数えない。空 prefix root は LCP 長に寄与しない。
復習の核
- LCP=共有prefix数という等式を短い二文字列で確認する。Trie node の count が「末端数」でなく「通過文字列数」であることに注意する。
計算量と制約
時間
O(L)、L=Σ|S_i|。trie通過頻度。
空間
O(L)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 3\times 10^5; S_i is a string consisting of lowercase English letters.; 1 \leq |S_i|; |S_1|+|S_2|+\ldots+|S_N|\leq 3\times 10^5; All input numbers are integers.
出典