方針

2つの配列の畳み込み

\[c_i = \sum_{j = 0}^i a_j b_{i - j}\]

のような形式にすると、AC-Library の convolution で問題を解くことができます。

解答

畳み込みの \(a, b\) が \(-1, 1\) からなる配列ならば「\(a_j = b_{i - j}\) ならば \(a_j b_{i - j}=1\)」「\(a_j \neq b_{i - j}\) ならば \(a_j b_{i - j}=-1\)」となります。

よって、 \(S, T\) を \(0, 1\) からなる配列とみなして、\(0\) を \(-1\) に置換します。

また、畳み込みの形式にするために \(S\) の前後を反転させた配列 \(S'\) を用います。

そうすると、

\[R_i = \sum_{j = 0}^i T_j S'_{i - j} = \sum_{j = 0}^i T_j S_{(|S|-i) + j}\]

となる配列を求められます。

\(S, T\) の一致する箇所の個数が最大のとき \(R\) が最大となります。

また、\(R\) のうち有効なのは \(T\) のすべての要素が使われている範囲なので、

\[(|T| - \max_{|T| - 1 ≤ i < |S|} R_i)/2\]

が答えになります。

解答例 C#