ABC 324 E — Joint Two Strings

考察

各S_iについて、Tのprefixをsubsequenceとして何文字取れるかA_iと、Tのsuffixを何文字取れるかB_iを独立にgreedy scanで求められる。

concatenation S_i+S_jがTを含むことは、Tの先頭A_i文字を前半で、残りを後半で取れるA_i+B_j≥|T|と同値である。

従ってiを固定した良いjの数は、B_j≥|T|-A_iを満たす文字列数という1次元threshold queryになる。

採用する候補: 各文字列のprefix-match長Aとsuffix-match長Bを求め、Bの頻度suffix sumで全ordered pairを数える。

棄却する候補: 全ordered pair(i,j)についてS_i+S_jを作り、Tのsubsequence判定を行う。

N≤5×10^5でpair数N^2が大きく、連結文字列生成も不要である。

棄却する候補: S_i単体がTを含むかだけを数える。

Tのprefixとsuffixを2本の文字列へ分担して初めて成立するpairを落とす。

各S_iを左からscanしてA_i、右からscanしてB_iを求める。count[b]へB_iの頻度を入れ、ge[l]=Σ_{b≥l}count[b]をsuffix sumする。各iについてl=|T|-A_iを計算してge[l]をanswerへ加え、64bit整数で出力する。

典型の発動条件

subsequenceのgreedy match長

発動条件: 固定patternのprefix/suffixを多数文字列がどこまで含むか求めるとき。

pattern pointerを一方向scanで進める。

pair条件のthreshold集計

発動条件: ordered pair条件がA_i+B_j≥Lの形になるとき。

B頻度のsuffix sumで各A_iの相手数を得る。

問題固有の要素

連結境界を跨ぐsubsequenceは、Tのどこで前半から後半へ担当を切り替えるかだけで、各側の最大match長の和へ圧縮できる。

別の問題へ持ち帰る視点: concatenation上のsubsequence条件では、patternのprefix/suffixを各部分へ割り当てる境界parameterを探す。

正当性

subsequenceとして取れるprefix最大長はS_iを左からT pointerと照合するgreedy、suffix最大長は両文字列を右から照合するgreedyで得られる。 A_i最大長まで前半で取れるなら、それより短いprefixも取れるため、残りsuffixの長さだけが後半への必要条件になる。 全N^2 pairを調べず、文字列scan総長と|T|の前計算だけで各iの相手数を得られる。

実装上の注意

  • B_iはT suffixの長さとして0..|T|で数え、右scanのpointer方向と長さ換算を混同しない。
  • 答えは最大N^2で32bitを超えるため64bit整数を使う。

復習の核

  • Tを前半と後半へ複数の位置で分けられる例を作り、最大A_iと最大B_jの和だけで存在判定できることを確認する。

計算量と制約

時間

O(L+N+len(T))、L全S文字数、greedy prefix/suffixと頻度suffix和。

空間

O(N+len(T)+L)入力込み。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: N is an integer.; 1 \leq N \leq 5 \times 10^5; S_i and T are strings of length 1 to 5 \times 10^5, inclusive, consisting of lowercase English letters.; The total length of S_1, S_2, \ldots, S_N is at most 5 \times 10^5.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Joint Two Strings の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

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

      主タグ: 寄与の数え上げと順序交換

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

      学習の位置

      体系上の位置: 局所寄与へ分解して集計順を交換する

      • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

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

      • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題