まとまった内容ではありませんが、（コンテスト問題に対して解法解説とかをやらなくなったものあって）記事投稿頻度が減ったぶんの埋め合わせにしようと思います。
動機
（私の作問でも私の投稿でもありません）
問題概要
正整数 $A$ , $B$ , $L$ , $R$ および文字列 $S$ , $T$ が与えられます。 $T$ は短く、 $S$ は長いものとします。 $T$ を $k$ 回繰り返した文字列を $T^k$ 、文字列 $X$ , $Y$ の編集距離(レーベンシュタイン距離) を $d(X,Y)$ と表すとき、次の値を求めてください。
$$\max_{L\leq k\leq R, k\in\mathbb{Z}}Ak-Bd(S,T^k)$$
メインの主張
$S$ , $T$ を文字列とします。このとき次で定義する上三角行列 ( $0\leq l\leq r\leq |S|$ について、 $(i,j)$ 要素を $A_{l,r}$ とします) は Monge です。
- $A_{l,r}$ の値を $S[l..r)$ と $T$ の編集距離とします。ただし、
- $S[l..r)$ は $S=S_0S_1\ldots S_{|S|-1}$ の部分文字列 $S_lS_{l+1}\ldots S_{r-1}$ です。
- 「編集距離」はレーベンシュタイン距離を指します。
証明
文字列 $X$ , $Y$ の編集距離は、あるグラフの最短距離に帰着することで $O(|X||Y|)$ 時間で計算できます。特に、このグラフは平面グラフです。さらに、片方がある文字列の部分文字列として動く場合、編集距離は帯状のグラフを横切るような経路の最短距離が対応します（図）。
Monge 性の四角不等式に対応するパスを考えます。不等号を $\geq$ としたときの左辺に対応する $2$ つのパスのうち、コストの最小値を達成するものをとります。グラフ全体が平面グラフであることと、始点終点の位置関係より、この $2$ つのパスはある頂点で交差します。よって、コストの和を変えずに始点終点の組を変えることができて、そうすると右辺に対応するパスが得られます（図）。よって、四角不等式が成立し、上三角行列の Monge 性が示されました。
解法
まず $S[l..r)$ と $T$ の編集距離をオンラインクエリとして高速に求められるようにします。編集過程で $T$ をどのように得るかは、 $T$ の各文字それぞれをどのように得るか $3$ 通り（ $S$ の文字を残す / $S$ の文字を書き換える / 挿入する）を考えれば、 $3^{|T|}$ 通りに分けられます。それぞれが実行可能かどうかは、 $S[l,r)$ から貪欲に取り出せば判定できるので、適切な前計算のもとで $1$ 文字あたり $O(1)$ 時間で判定できます。よって、求める編集距離は $O(3^{|T|})$ 時間で得られます。
$S$ を $k$ 個の部分文字列に分割してそれぞれ $T$ との編集距離をとったものの総和を考え、すべての分割方法についてその最小値をとれば、 $S$ と $T^k$ の編集距離に一致します。もし、分割後の文字列に空文字列を許さなければ、単に $k$ を固定した最大化問題は Mongeグラフ上の $k$-辺最短路問題です。空文字列を許す場合も凸性を保つので、対応する遷移を追加すれば問題としては処理できます。
$k$ の範囲が制約されていますが、 $O(|S|\log (B(|S|+|T|)))$ 回のクエリで最大値を計算できます。