概要

この問題は以下の手順で解くことが出来ます。

1. \(S\) と \(T_1,\ldots,T_N\) を連結した文字列に対する接尾辞配列(以下SA)とLCP配列(以下LA)を構築する
2. \(i=1,2,\ldots,|S|\) に対し、\(S\) の \(i\) 文字目を \(1\) 文字目とする部分文字列であって \(T_1,\ldots,T_N\) のいずれかに一致するようなもののうち長さ最小のもの(の長さ)を求める
3. 区間 \([l_1,r_1], [l_2,r_2], \ldots\) に対し、すべての \(i\) について \([l_i,r_i]\) に \(1\) つ以上 * が含まれる、という条件を満たすように操作をするとし、操作回数の最小値を求める。

SA・LAの構築

文字列 \(X\) であって部分文字列として \(S, T_1, \ldots, T_N\) が現れるようなものを作ります。例えば入力例 \(1\) では, \(X=\) abcdefghijklmn_abcd_ijk_ghi といった塩梅です(方針や今後の処理にもよりますが、区切り文字は入れた方が無難です)。そして、これに対してSA・LAを構築します。これはACLに存在するので、慣れていない方はドキュメントをご覧になった上で使うと良いでしょう。
ここで、LAについて、今後の処理の前提となる説明をします。ドキュメントにあるように、LAはSA上で隣り合う \(2\) つの接尾辞のLCPを表す配列です。また、SA上で隣り合うとは限らない \(2\) つの接尾辞に関しても、その間にあたるLAの値の最小値がLCPとなります。ゆえに、区間最小値を取得できるセグメント木に載せれば \(\mathrm{O}(\log |S|)\) で任意の接尾辞同士に対してLCPを求めることが出来ます。さらに、今回作った \(X\) に対してこれを用いると、\(T_i\) の開始位置と \(S\) の \(j\) 文字目のLCPが \(|T_i|\) 以上となるかどうかを調べることで \(S\) の \(j\) 文字目から始まる部分文字列が \(T_i\) と一致するかどうかを調べられます。

\(S\) の \(i\) 文字目から何文字分がある \(T_i\) と一致するか調べる

たとえば \(S=\) abc、\(T_1=\) ab、\(T_2=\) abc の時、\(S\) の \(1\) 文字目から \(2\) 文字目までが \(T_1\) と、\(1\) 文字目から \(3\) 文字目までが \(T_2\) と一致します。ここで、明らかに \(1\) 文字目から \(2\) 文字目までのどこかで * への置換が行われて \(T_1\) がそこに現れないようにされたとき、\(T_2\) もそこに現れないようになっています。このように、\(i=1,2,\ldots,|S|\) に対し、\(i\) 文字目を左端とする部分文字列のうち \(T_i\) に一致するようなものは、長さが最小のものだけを考えれば十分です。 すべての \(i\) に対してそのような部分文字列の長さの最小値を求めるには、LAを使って以下のようにすればよいです。

• 平衡二分木を、SA上のすべての位置が入った状態で初期化する
• \(T_1,\ldots,T_N\) に対し、\(|T_i|\) が小さい方から順に次の処理を行う
  • LAを載せたセグメント木で二分探索を行い、\(T_i\) と一致するような接尾辞を表すSA上の区間を求める
  • 求めた区間内に含まれる値を平衡二分木から取り出し、その接尾辞の先頭から含まれる \(T_i\) の長さを \(|T_i|\) として記録、そして平衡二分木からその値を削除する

あるいは、\(|T_i|\) が大きい方から順に遅延セグメント木で区間更新を行う、という方法もあります。

区間をすべて被覆するような操作回数の最小値を求める

ここまでの処理を行うと、問題は「操作を何回か行って、高々 \(|S|\) 個の区間に対し、それぞれの区間内に \(1\) 個以上 * が含まれるようにしたい。最小で何回操作をする必要があるか」というものになります。これは右端でソートして貪欲にシミュレーションをすれば良いです。(参考 : この部分とほとんど同じ過去の問題)