ABC 284 F — ABCBAC

考察

Tの前半をA=T[0,N)、後半をreverseした列をB=reverse(T[N,2N))とすると、切れ目iの条件はA[0,i)=B[N-i,N)かつA[i,N)=B[0,N-i)になる。

各iを直接比較すると合計が二次になるが、両条件は固定した2本の連結文字列上のprefix一致長として一括計算できる。

採用する候補: A+BとB+AのZ-arrayを求め、各切れ目iで必要な2つの一致長をO(1)判定する。

全iのprefix/suffix一致を線形時間で準備でき、条件を満たすSも元のTから直ちに復元できる。

棄却する候補: i=0..Nごとに候補Sを作り、生成した長さ2Nの文字列とTを比較する。

N+1候補それぞれに線形比較が必要でO(N^2)になる。

棄却する候補: rolling hashで2区間の一致を判定する。

高速化はできるが衝突管理が必要で、この完全一致判定には決定的なZ算法で十分である。

X=A+Bでは位置2N-iからのprefix一致がA[0,i)=B[N-i,N)を、Y=B+Aでは位置N+iからの一致がB[0,N-i)=A[i,N)を表す。

条件を満たすとき、SはT[0,i)+T[N+i,2N)であり、中央のreverse(S)を改めて構築して探索する必要はない。

A=Tの前半、B=後半のreverseを作り、X=A+BとY=B+AのZ-arrayを計算する。i=0..Nについて、i=0なら第1条件、i=Nなら第2条件を空文字として扱い、それ以外はZ_X[2N-i]≥iかつZ_Y[N+i]≥N-iを確認する。最初の成立iでS=T[0,i)+T[N+i,2N)とiを出力し、なければ-1を出す。

典型の発動条件

Z algorithm

発動条件: 同じpatternとの一致長を多数の開始位置で知りたいとき。

2つの連結文字列のZ-arrayで全切れ目の区間一致をO(1)判定する。

reverseによる向きの統一

発動条件: 条件にreverse文字列とのsuffix/prefix比較が混在するとき。

後半をreverseして、両条件を通常のprefix一致へ変換する。

問題固有の要素

生成式をSそのものではなくTの前半Aと後半を反転したBの対応へ書き換えると、未知文字列が消えて切れ目iだけの判定になる。

別の問題へ持ち帰る視点: 未知列を含む文字列構成問題では、観測済み区間同士の等式へ消去してから文字列algorithmを選ぶ。

正当性

切れ目iを固定すると候補SはT[0,i)+T[N+i,2N)に一意に決まり、中央のT[i,N+i)がそのreverseであることが必要十分。A=T前半、B=reverse(T後半)を作ると条件は二つのprefix一致へ分かれる。A+BとB+AのZ値でそれぞれの必要長を判定できるため、全i=0..Nを調べれば解を漏らさない。長さ0の一致は真として配列末尾の参照を避ける。

実装上の注意

  • i=0,Nでは参照位置が配列末尾になる条件があるため、長さ0の比較を先にtrueとして扱う。
  • Sの後半はT[N+i,2N)から取り、T[i,N)と取り違えない。

復習の核

  • AとBをN=3程度で横に並べ、各iの2区間がX,YのどのZ値へ対応するかと、復元したSをreverseしてTが戻るかを確認する。

計算量と制約

時間

O(N)。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N \leq 10^6; N is an integer.; T is a string of length 2N consisting of lowercase English letters.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: Z algorithmによるprefix matching

主題
  • Z algorithmによるprefix matching: 既知のZ-boxを再利用してZ arrayを線形時間で構成し、各位置から始まる接尾辞と文字列全体のprefixの最大一致長を、文字列連結によるprefix照合へ利用できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: Z algorithmによるprefix matching

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

      学習の位置

      体系上の位置: Z algorithmによるprefix matching

      • 既知のZ-boxを再利用してZ arrayを線形時間で構成し、各位置から始まる接尾辞と文字列全体のprefixの最大一致長を、文字列連結によるprefix照合へ利用できる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題