考察
同じ文字列を何通りの位置から取り出せても、答えには一度だけ数える。そこで、二コピーをつなげた全体を「各文字をできるだけ左から取る」という規則で一意に表す。後半の先頭位置を仮に固定して二コピーを同時に伸ばし、全体の規則に合うものだけを答えに加える。
求めるのは、非空な文字列 のうち、二つ連結した が入力文字列 の部分列となるものの種類数である。 とする。位置を選ぶ全探索は 通りある上に、その選び方の個数は答えと異なる。例えば S=aaa から aa を取る位置は の3通りだが、対応する T=a の寄与は1である。
一つの文字列を左から順に作るとき、次の文字は直前に選んだ位置より右にある同じ文字のうち、最も左のものから取ればよい。早く取るほど後ろに使える部分が広く残るため、取り出せる文字列をこの規則で取り逃すことはない。こうして各文字列に一つの取り出し方を対応させる。
位置は1始まりとし、 を「位置 より厳密に右で文字 が最初に現れる位置」と定義する。存在しなければ番兵 を返す。 は文字列の先頭より前を表す。 と英小文字26種類について表を用意する。行 をすべて とし、右から左へ、行 を行 のコピーで作った後に とすれば、 時間で前計算できる。
二コピーを全体として最左から取るには、後半の先頭を、前半の末尾の直後から探す必要がある。しかし、前半の末尾は を作り終えるまで分からない。そこで後半の先頭位置 を先に固定し、前半・後半の各コピーをそれぞれ最左から伸ばす。前半の現在の末尾を とすると、 を保てば二コピーは順番どおりに並ぶ。ただし、これだけで重複は消えるだろうか。
先ほどの S=aaa, T=a をこの方針で取り出すと、前半先頭は位置1、後半先頭 は2または3となる。両方とも を満たし、各コピーの中では最左から取っているが、全体 TT=aa の最左の取り出し方は だけだ。
つまり、各コピーの内部を最左化することに加えて、コピー間のつなぎ目も最左であると確かめる必要がある。後半の先頭文字は なので、現在の文字列を完成した として数える条件は
となる。この条件が、仮に選んだ と、 全体を最左から取ったときの後半先頭を一致させる。
具体的には、 を一つずつ固定して次のDPを行う。 の先頭文字は と決まるため、前半先頭を とする。 ならこの は使えない。それ以外は 、その他を0として始める。最初から1文字選んでいるので、空の は含まれない。
は、ここまでに作った同じ非空文字列を前半では の先頭から、後半では固定した位置 から、それぞれ最左の出現へ進んで取り出したとき、末尾が となる文字列の種類数とする。有効な添字は である。次に同じ文字を付け足せるかどうかは、この末尾の対と だけで決まるため、異なる文字列が同じ状態に集まったら個数を足してよい。
次の1文字 を26種類から選び、
とする。 かつ のときだけ、
と更新する。位置の選び方を分岐させず、追加する文字だけを選ぶ遷移である。両添字は厳密に増えるので、 を昇順、その内側で を昇順に走査すればよい。
各状態では、終了条件 を満たす場合だけ を答えへ一度加える。固定した からの寄与は
となる。集計後も次文字への遷移は続ける。また、今は終了条件を満たさなくても、延長後に満たす場合があるので状態を捨てない。全ての について集計し、加算は法 上で行う。
例えば S=aaaa では、 の初期状態 が T=a を数える。 の初期状態 は数えないが、a を付け足すと へ進み、 なので T=aa を数える。 の初期状態も数えず、延長時は後半の次位置が番兵 となるため遷移を捨てる。答えは a と aa の2種類である。
集計した状態からの延長も必要で、例えば S=abab の では、 で T=a を数えた後、b を足した で T=ab も数える。
典型の発動条件
distinct subsequenceのcanonical embedding
発動条件: 同じ文字列を得る位置の選び方が複数あっても、文字列の種類数を数えたい。
各文字を可能な限り左の出現から取ると、後続の選択を狭めずに代表となる取り出し方を一つに固定できる。複数の部分を組み合わせる場合は、それぞれの内部だけでなく、つなぎ目も代表の規則と一致するかを確認する。
二列同期遷移DP
発動条件: 同じ未知文字列を二つの部分列として同時に作りたい。
二つの末尾位置を状態にし、同じ次文字で両方を進める。次の出現位置を一意に決めれば、DPの値は取り出す位置の選び方の個数ではなく、生成した文字列の種類数を表せる。
問題固有の要素
二つの同じコピーを前後に置くため、後半の先頭位置を固定すると、その文字と前半の先頭位置も決まる。残る全体の最左規則は、前半末尾から後半先頭へ移る一か所だけで検査できる。
別の問題へ持ち帰る視点: 部分ごとに代表を決めても、組み合わせ全体の代表が一意になるとは限らない。境界を固定し、最後に境界をまたぐ規則を確かめる。
正当性
に含まれる任意の非空文字列 を考える。各文字を直前の位置より右の最左の出現から取る方法は、他の取り出し方より各位置が右にならないため、必ず最後まで成功する。この方法は一意であり、後半先頭位置 も一意に決まる。前半の全位置は より左なので、その文字列は対応する のDPで初期化から順に同じ文字を選ぶ遷移をたどれる。前半末尾を とすると も満たすため、必ず答えへ加えられる。
逆に、DPで集計した状態は、前半末尾が で、二つのコピーが同じ文字列を表す有効な部分列である。前半の取り出しは先頭からの最左規則に従い、終了条件が後半の先頭でも同じ規則を保証し、後半の残りも最左遷移に従う。従って、その取り出し方は 全体の一意な最左の取り出し方に一致する。
固定した と文字列 に対して、選ぶ文字列と各次位置は一意なので、DP内で同じ を複数回生成しない。異なる で同じ を集計することも、全体の最左の取り出し方の一意性に反する。よって各 は漏れなく一度だけ数えられる。
実装上の注意
- は「現在位置より厳密に右」を返す。同じ位置の文字を再利用しない。
- 次位置が番兵 の遷移は捨てる。 と を確認すれば、両方の消失を除ける。
- 初期化前に の場合を除く。長さ1から始めるため、空の は答えへ加わらない。特に では有効な初期状態がなく、答えは0になる。
- 終了条件は答えへの集計条件であり、遷移を止める条件ではない。成否にかかわらず延長を試し、各状態は一度だけ集計する。
- ごとにDPを0へ戻し、前の の結果を混ぜない。DPと答えへの加算のたびに法 を取る。
復習の核
- 「位置の選び方」と「得られる文字列の種類」を区別し、各文字列の代表となる取り出し方を決める。
- 部分ごとの最左化だけで重複が消えるかは、
aaa の と で確かめる。境界をまたぐ最左規則も必要である。
- 短い文字列を数えた状態も、まだ数えられない状態も延長できる。集計条件と遷移条件を分ける。
計算量と制約
時間
次出現表の前計算に 時間。固定した ごとにDPの初期化・走査・集計は 、各状態から高々26文字の遷移を行うので 時間となる。 は高々 通りで、全体は 時間。
空間
一つの のDPが 、次出現表が 、入力が 。 を一つずつ処理して同じDP領域を使い回すため、全体は 領域。
制約との対応
、文字は英小文字26種類。遷移候補は高々 回で、位置の全探索を避けて処理できる。答えは種類数を で割った余りとして求める。制限時間は2秒、メモリ制限は1024 MiB。
出典