考察
全substring tripleは総数Mが二次規模になり得るため実体化できないが、各substringはある元string suffixの非空prefixとして一意に表せる。
suffixを辞書順に並べると、同じprefix文字列を持つsuffixはLCP条件で連続区間になり、その文字列のoccurrence tripleも連続blockとして数えられる。
採用する候補: 全stringをseparator付きで連結してsuffix array/LCPを作り、LCP intervalをmonotone stackで辞書順blockへ圧縮し、query rankを累積個数から逆算する。
suffix総数は10^5で、最大二次個のsubstring occurrenceをO(total length)個のLCP blockとして扱える。
棄却する候補: 各suffixの全prefix tripleを生成し、文字列比較でsortする。
substring数Mが各|S_i|²の和で、memory・sortingとも制約を超える。
separatorを全英小文字より小さく置いた連結stringのsuffix順は、separatorで切った各元suffixの辞書順を保つ。LCPは元string末尾までにcapする。
TのSA順の葉と隣接LCPから、圧縮prefix木を作る。内部nodeの深さは共有prefix長、葉の深さは元文字列内の残りsuffix長であり、separatorを含めない。
stackにはrootから右端の内部nodeまでを深さ昇順で持つ。次の葉を加える前に直前の葉とのLCP=hを読み、深さ>hのnodeをpopする。pop済み部分木は既に親へ接続されているので、最後にpopした部分木(popがなければ直前の葉)を直前の子とする。stack上端の深さ<hなら深さhの内部nodeを作り、親の最後の子をそのnodeへ付け替え、直前の子をその下へ移す。深さ=hなら既存nodeを使う。新しい葉をその末尾の子へ追加する。このpop・付け替えで各nodeを一度ずつ作り、子のSA順も保てる。
親深さaから子深さbへの枝に対して、子の葉範囲[i,j]と長さ帯(a,b]が一blockになる。葉でも同じ扱いで、bは残りsuffix長。suffixが別suffixのprefixだったり同一suffixが複数あったりする場合、深さが等しい葉を許し、長さ0の枝は出力しない。その葉も祖先blockの多重度には含める。
辞書順走査では、枝の長さa+1,…,bを短い順に先に出し、その後で子の枝をSA順に辿る。prefix自身はそれを延ばした文字列より小さいから、この順序でよい。S="ab"ならrootの子の葉は"ab"と"b"で、前者の枝が"a","ab"、後者が"b"を出す。
blockの多重度m=j−i+1、個数m(b−a)を累積し、queryが入ったblock内の0-based offsetをtとする。長さR=a+1+floor(t/m)、出現はT[i+(t mod m)]から取る。出現が元文字列Kの位置Lなら(K,L,L+R−1)を出す。同一文字列の出現順は任意でよく、昇順queryとblockを一緒に走査できる。
典型の発動条件
suffix arrayとLCP
発動条件: 多数のsuffix/prefix由来文字列を辞書順に扱い、共通prefix区間を知りたいとき。
全suffixをsortし、隣接LCPから同prefixを共有する連続範囲を得る。
LCP intervalのmonotone stack
発動条件: suffix tree相当のprefix groupを明示treeなしで線形列挙したいとき。
LCPの増減をstackで管理し、有効なsuffix区間と深さ範囲をblock化する。
巨大sorted multisetのrank selection
発動条件: 要素総数は巨大だが等値groupのsizeを圧縮して順に数えられるとき。
block累積数でrankをlocateし、block内offsetから代表要素を復元する。
問題固有の要素
substringの辞書順multisetは、suffix順とLCP intervalごとのprefix長帯(a,b]を組み合わせると線形個の長方形blockに分解できる。
別の問題へ持ち帰る視点: quadraticなsubstring occurrenceを扱うときは、suffixを起点にし、同prefixのoccurrence区間×長さ区間として圧縮する。
正当性
全substring occurrenceは各有効suffixの非空prefixと一対一対応する。SAと元文字列末端でcapしたLCPは、同じprefixを持つsuffix群の連続区間を与える。LCP stackで辞書順に、長さ(a,b]とsuffix区間[i,j]のblockを列挙すると、各長さにj−i+1個の等しいoccurrenceがありblock個数は(b−a)(j−i+1)。全blockはprefixを過不足なく分割する。累積個数と昇順のrank質問を同時走査し、block内の長さとoccurrenceへ逆算すれば正しい順位を復元できる。
実装上の注意
- separatorを跨ぐLCPを元suffix長で必ずcapし、separator始まりsuffixと空prefixをTから除外する。
- Mとblock累積は文字列長の二次規模で32 bitを超え得るため64 bitを使い、block内のequal occurrenceは任意順でよいという出力許容を利用する。
復習の核
- suffix群abab,bab,ab…のprefixをLCP区間へ並べ、同じ'ab'が区間[i,j]・長さR=2のmultiplicityとして現れることを手で確かめる。
計算量と制約
時間
SA-ISと線形LCP/stack構成でO(L+Q)。L=Σ|S_i|+N。
空間
O(L+Q)(全回答を保持する場合)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^5; 1 \leq \lvert S_i\rvert \leq 10^5; \displaystyle\sum_{i=1}^N \lvert S_i\rvert\leq 10^5; 1 \leq Q \leq 2\times 10^5; 1 \leq x_1<x_2<\cdots<x_Q \leq \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}; N,Q,x_1,x_2,\ldots,x_Q are integers.; S_i is a string consisting of lowercase English letters.
出典