回文半径と左右対称区間を特定する
概要
回文半径・Manacher
各中心の最大回文半径を左右対称性と既知区間の再利用で線形に求める。
考え方
奇数半径
0-indexの文字列Sについてd1[i]を、中心iの最大奇数回文 S[i−d1[i]+1:i+d1[i]] の半径とする。一文字を含むのでd1[i]≥1である。既に求めた回文のうち右端が最大の閉区間[l,r]を持ち、最初はl=0,r=−1とする。
iを左から順に処理する。i>rならk=1、i≤rなら鏡像j=l+r−iを使い k=min(d1[j],r−i+1) と初期化する。S[l:r+1]の対称性から区間内の一致は移せるが、外側はまだ不明なのでrで切る。次に i−k≥0、i+k<N、S[i−k]=S[i+k] の間kを増やす。d1[i]=kとし、i+k−1>rならl=i−k+1,r=i+k−1へ更新する。
偶数半径
d2[i]はi−1とiの間を中心とする最大偶数回文 S[i−d2[i]:i+d2[i]] の半径であり、空なら0。独立にl=0,r=−1から始め、i>rならk=0、そうでなければ k=min(d2[l+r−i+1],r−i+1) とする。比較する新しい両端はi−k−1とi+k。範囲内で等しい間kを増やしd2[i]=kとする。右端を更新するならl=i−k,r=i+k−1になる。奇数と鏡像添字が1ずれるのは、中心が頂点ではなく隙間だからである。
半径を区間判定へ戻す
半開区間[a,b)の長さm=b−aが奇数ならi=(a+b−1)/2として d1[i]≥(m+1)/2、偶数ならi=(a+b)/2として d2[i]≥m/2 と同値である。空区間は回文として別処理する。全非空回文の出現数は Σ_i(d1[i]+d2[i])。各中心で半径1,…,dの回文を一つずつ得られ、中心と長さが出現区間を一意に定めるためである。
鏡像の回文が既知区間内で終わるなら、その次の不一致も対称性で確定し、直接比較はそこで止まる。右端まで届く場合だけ新しい一致がrを進める。rは戻らず、不一致比較は各中心で高々一回なので、両走査とも総比較数は線形になる。
指定半径からの構成へ転用する
文字列から半径を求める場合と、半径を指定され文字列を構成する場合は仮定が異なる。後者では、内側の対称位置を等値制約、両端が存在する外側のpairを不等制約にする。全等値pairは二乗個になり得るため、鏡像から推移的に導かれる等値を省く。
ABC349 Gでは、指定半径Aを持つ列が存在する場合に限って、鏡像回文とその外側pairが既知回文内へ厳密に収まる中心を省ける。境界に達する等号の場合は外側の不一致を反射できないので、省略せず次の中心として処理する。DSUで等値を縮約して不等辺を彩色した後、生成列の半径を通常のManacherで全照合する。この照合が、存在を仮定した圧縮を判定手順へ変える。
正当性は「存在する入力なら制約を失わず必ず構成できる」「全照合に通った候補は合法」の二方向で示す。計算量は存在しない入力にも保証し、union中にだけ進む右端と中心cursorの単調性から評価する。条件付きの制約圧縮と無条件の仕事量の上界を混同しない。
成立条件と計算量
長さNに対しO(N)時間・空間、前処理後の一つの区間回文判定はO(1)。空文字列では空配列を返す。奇数・偶数で別の最右区間を保ち、片方の鏡像式をもう片方へ流用しない。半径の和は異なる回文文字列数ではなく、位置の異なる出現区間数である。
問題一覧
- ABC398 F「ABCBA」 公式問題
- ABC349 G「Palindrome Construction」 公式問題
技能・出典
主題: 回文半径と左右対称区間を特定する(各中心の回文半径を求め、左右対称な区間の成立条件を判定できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 回文半径・Manacher / 補助タグ: 構成解・witness復元、DSUによる連結成分管理・縮約
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。中心の左右対称性と既知区間を再利用し、奇数長・偶数長の回文半径を求める。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 文字列アルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-palindrome-radius
習得する技能
- 各中心の回文半径を求め、左右対称な区間の成立条件を判定できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
各中心の左右一致を半径としてまとめ、回文区間の判定と列挙へ利用する。
このUnitでは扱わないもの
- 一般の部分文字列hash比較と、接尾辞・LCPの索引。