ABC 346 F — SSttrriinngg in StringString

考察

要求される文字を左から順に、できるだけ早い出現へ対応させる。反復文字列では同じ文字の出現間隔も周期的なので、何個も先の出現へ一度に移動できる。この判定を使い、各文字を何回ずつ要求できるかを二分探索する。

まず二種類の繰り返しを区別する。f(S,N)f(S,N) は SS 全体を NN 回連結した文字列だが、g(T,k)g(T,k) は TT の各文字を順に kk 個ずつ並べた文字列である。例えば T=abT=\texttt{ab} なら、g(T,3)=aaabbbg(T,3)=\texttt{aaabbb} となる。求めるのは連続とは限らない部分列なので、対応させる文字の間は読み飛ばしてよい。

s=∣S∣s=|S|、L=NsL=Ns とおく。LL は最大 101710^{17} なので、f(S,N)f(S,N) を実際に構築したり、要求する文字を一つずつ探したりする方法では間に合わない。一方、kk を固定すると、TT の各文字について「この位置以降で同じ文字を kk 個拾う」という操作を ∣T∣|T| 回行えばよい。このまとまりを一度に処理する方法を考える。

次に探す位置から、出現順位を求める

文字列の添字はすべて0始まりとする。状態 pospos は「次に文字を探し始める位置」で、初期値は0である。k>0k>0 のとき、文字 cc を kk 個拾ったら、最後に使った添字の 1つ後 へ進める。これにより同じ文字位置を再利用しない。k=0k=0 なら要求列は空なので、文字の有無を調べる前に成功とする。

一周期 SS に含まれる文字 cc の位置を、昇順の配列 PcP_c に記録する。SS を左から走査して追加すれば、別途ソートする必要はない。以下では m=∣Pc∣>0m=|P_c|>0 とする。m=0m=0 なら、正の個数を要求する判定は失敗である。

現在位置を、周期番号 qq と周期内の位置 rr に分ける。

q=⌊poss⌋,r=pos mod sq=\left\lfloor\frac{pos}{s}\right\rfloor,\qquad r=pos\bmod s

PcP_c の中で rr 以上となる最初の要素の添字を jj とする。これは lower_bound(P_c, r) で求められ、該当する要素がなければ j=mj=m とする。この周期にはまだ使える出現が m−jm-j 個残っている。

ここで周期番号 qq の先頭から、文字 cc の出現に0始まりの通し番号を付ける。現在位置以降で最初の出現の番号は jj だから、求める kk 番目の番号は

t=j+k−1t=j+k-1

となる。一周期に mm 個ずつ出現するので、tt を mm で割った商が進む周期数、余りがその周期内での出現の添字になる。従って更新式は

pos←(q+⌊tm⌋)s+Pc[t mod m]+1pos\leftarrow \left(q+\left\lfloor\frac{t}{m}\right\rfloor\right)s +P_c[t\bmod m]+1

である。これは無限に反復した場合の位置を表す式であり、有限の NN 周に収まるかは別に確認する。実装では後述のとおり、周期番号を検査してから積を作る。

j=mj=m でも場合分けは増えない。k=1k=1 なら t=mt=m なので、商が1、余りが0となり、次周期の最初の出現へ進む。例えば S=abacaS=\texttt{abaca}、pos=2pos=2、c=bc=\texttt{b} なら Pc=(1)P_c=(1) であり、今の周期には出現が残っていない。次周期の添字6を使い、pos=7pos=7 になる。

同じ S=abacaS=\texttt{abaca} で c=ac=\texttt{a} を探すとき、Pc=(0,2,4)P_c=(0,2,4) である。pos=4pos=4、k=3k=3 なら q=0,r=4,j=2,t=4q=0,r=4,j=2,t=4 となる。商は1、余りは1なので、更新後は pos=5+2+1=8pos=5+2+1=8。実際に使う添字は4、5、7であり、最後に使った7の次から探索を続ける。

境界も同じ式で扱える。次の表はすべて c=ac=\texttt{a} の例で、必要なだけ周期が続くとしている。

更新前の posposkk使う添字更新後の pospos確かめる境界
4145周期末の文字を使い、次周期の先頭が次探索位置になる
5156周期境界から探すと、その位置の文字を使える
122, 45今の周期の残り2個をちょうど使い切る
474, 5, 7, 9, 10, 12, 1415複数周期をまたいでも商と余りで決まる

判定を組み合わせ、最大の回数を探す

feasible(k) は k=0k=0 なら成功、そうでなければ pos=0pos=0 から始め、TT の文字順に上の更新を行う。各更新が pos≤Lpos\leq L に収まれば続け、はみ出すならその場で失敗とする。すべての文字を処理できれば成功である。pos=Lpos=L は最後の文字まで使った状態なので、それが最後の要求なら成功だが、さらに正の個数を要求することはできない。

0≤k1<k20\leq k_1<k_2 のとき、g(T,k2)g(T,k_2) の各文字のまとまりから k2−k1k_2-k_1 個ずつ削ると g(T,k1)g(T,k_1) が得られる。従って大きい kk で照合できるなら、小さい kk でも照合できる。単に長さが増えるだけでなく、この削除による包含が判定の単調性を保証する。

要求列の長さは k∣T∣k|T| なので、答えの上限を U=⌊L/∣T∣⌋U=\lfloor L/|T|\rfloor とできる。成功側を ok=0ok=0、失敗側を ng=U+1ng=U+1 と置く。ngng では要求列が元の文字列より長いため必ず失敗する。ng−ok>1ng-ok>1 の間、mid=ok+⌊(ng−ok)/2⌋mid=ok+\lfloor(ng-ok)/2\rfloor を判定し、成功なら ok=midok=mid、失敗なら ng=midng=mid とする。終了時の okok が答えである。

典型の発動条件

周期文字列上のk-th occurrence jump

有限の文字列を巨大な回数反復し、指定文字の多数回先の出現を求めたいときに使う。一周期内の出現位置と個数を持ち、出現順位を商と余りへ分けることで、文字も周期も一つずつ走査せずに済む。

部分列の照合と組み合わせるときは、各要求を最早位置へ対応させても後続の選択肢を失わないことを確かめる。

答えの二分探索

最大化する量を固定すると可否を速く判定でき、成功する値が一続きの範囲をなすときに使う。この問題では小さい要求列を大きい要求列から削除して得られることが根拠である。判定器の正しさと単調性をそれぞれ示し、必ず成功する端点と必ず失敗する端点を用意する。

問題固有の要素

g(T,k)g(T,k) は各文字を kk 回ずつ要求するので、照合は ∣T∣|T| 回の出現順位の問い合わせにまとまる。TT 全体の繰り返しを探す処理と取り違えない。

似た定義が並ぶ問題では、短い文字列を一度展開して、同じ操作をまとめられる単位を確かめる。その単位に合わせて問い合わせを作ると、巨大な要求列も展開せずに扱える。

正当性

任意の有効な照合と比較する。要求文字を先頭から見たとき、貪欲法が使う位置は、対応する任意の照合の位置以下になる。最初は最早出現を選ぶためであり、途中でも前の文字をそれ以前に使えていれば、比較相手が使う次の出現を候補にできるためである。従って貪欲法が失敗した場合は他の照合も存在せず、成功した場合は実際に部分列を構成できている。

一文字を連続して kk 個要求するとき、最早の出現を順に拾った最後の位置は、現在位置以降での kk 番目の出現である。t=j+k−1t=j+k-1 を一周期の出現数 mm で割る操作は、その出現を周期番号と周期内順位へ一意に分解する。よって更新式は一文字ずつの貪欲法と同じ次探索位置を返す。周期番号が NN 未満なら使う文字は範囲内にあり、更新後の pos=Lpos=L も許される。範囲外なら照合は不可能である。空の要求 k=0k=0 も成功として扱うので、判定はすべての場合で正しい。

小さい kk の要求列は大きい kk の要求列から文字を削って得られるため、判定は成功から失敗へ一度だけ変わる。ok=0ok=0 は成功し、ng=⌊L/∣T∣⌋+1ng=\lfloor L/|T|\rfloor+1 は長さにより失敗する。二分探索はこの両端の性質を保ち、隣接した時点で最後の成功値を返す。

実装上の注意

  • pospos は次探索位置であり、最後に使った添字ではない。更新式の末尾の +1+1 を忘れると、同じ出現を次の要求にも使ってしまう。lower_bound は rr 以上を探すので、探索開始位置そのものも候補に含む。
  • k=0k=0 は最初に成功として返す。これにより t=j+k−1t=j+k-1 が負になる場合を避ける。TT に SS にない文字が含まれるなら、正の kk はすべて失敗するため、答えは0である。
  • L=Ns≤1017L=Ns\leq 10^{17} でも、失敗する候補の移動先が64bitに収まるとは限らない。例えば N=1012,s=105,∣T∣=1N=10^{12},s=10^5,|T|=1 で、要求文字が一周期に1個だけなら、探索上限 k=1017k=10^{17} の移動先は 102210^{22} 級になる。積を計算してから LL と比べるのでは遅い。
  • そこで B=q+⌊t/m⌋B=q+\lfloor t/m\rfloor を先に求め、B≥NB\geq N なら積を作らず失敗とする。B<NB<N のときだけ pos=Bs+Pc[t mod m]+1pos=Bs+P_c[t\bmod m]+1 を計算する。この値は NsNs 以下なので安全である。pos=Lpos=L の後に次の要求がある場合も、q=Nq=N となるため同じ検査で失敗する。
  • N,L,k,pos,t,BN,L,k,pos,t,B は符号付き64bit整数で扱い、最初の NsNs も64bitの積にする。探索範囲では k≤U+1≤1017+1k\leq U+1\leq 10^{17}+1、j≤m≤105j\leq m\leq 10^5 なので tt の加算は安全である。また、各更新前に pos≤Lpos\leq L を保つので q≤Nq\leq N であり、乗算前の BB の加算も64bitに収まる。

復習の核

  • 巨大な反復では、位置だけでなく「何番目の出現か」も商と余りで周期へ戻せる。
  • 部分列を貪欲に照合するときは、状態を「次に探す位置」と定める。最後に使った添字との1の差を、周期末と文字列末尾で確認する。
  • 回数を減らした要求が元の要求から削除して得られるなら、可否の単調性を示せる。長さの大小だけで単調と判断しない。
  • 答えが整数型に収まっても、失敗候補の途中計算ははみ出し得る。上限との比較を商の段階で行い、安全と分かってから掛ける。

計算量と制約

時間

U=⌊Ns/∣T∣⌋U=\lfloor Ns/|T|\rfloor とすると、前処理を含めて

O(∣S∣+∣T∣+∣T∣log⁡(∣S∣+1)log⁡(U+1))O\bigl(|S|+|T|+|T|\log(|S|+1)\log(U+1)\bigr)

である。位置列の構築は O(∣S∣)O(|S|)、不在文字の確認は O(∣T∣)O(|T|)。一回の判定では TT の各文字について lower_bound と定数回の整数演算を行うので O(∣T∣log⁡(∣S∣+1))O(|T|\log(|S|+1)) であり、二分探索は O(log⁡(U+1))O(\log(U+1)) 回判定する。U=0U=0 なら両端が最初から隣り合い、判定は不要である。∣S∣=1|S|=1 でも評価が消えないよう、対数内に1を加えている。

空間

O(∣S∣+∣T∣)O(|S|+|T|)。入力文字列と、合計 ∣S∣|S| 要素の文字別出現位置列を保持する。各判定の追加状態は定数個の整数だけであり、反復文字列や要求列は生成しない。

制約との対応

公式制約は 1≤N≤10121\leq N\leq 10^{12}、1≤∣S∣,∣T∣≤1051\leq |S|,|T|\leq 10^5 で、両文字列は英小文字からなる。制限時間は3秒、メモリ制限は1024 MiB。反復回数 NN は走査せず、二分探索の回数は高々57回である。一周期分の位置列だけを持ち、各移動も周期数によらず処理する。整数幅については、範囲外の移動を乗算前に棄却することが必要である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

SSttrriinngg in StringString の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 圧縮・反復・再帰文字列へ問い合わせる

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

    主タグ: 再帰・圧縮・入れ子文字列の走査

    補助タグ: 単調境界探索

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

    学習の位置

    体系上の位置: 圧縮・反復・再帰文字列へ問い合わせる

    • 圧縮・反復・再帰または入れ子で定義された文字列を展開せず、block長・対応区切り・作用から照会・変換・評価できる。

    先に読む単元:

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

    • 明示された文字列への接尾辞索引の構築。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題