KMP法から拡張KMP法へ：線形時間文字列照合の仕組み
総当たり照合の計算量課題
テキスト内の特定パターンを検索する最も単純な手法は、テキストの各位置を開始点とみなし、パターンと逐次比較する総当たり法です。このアプローチは実装が容易ですが、最悪ケースではテキスト長を $N$、パターン長を $M$ とした場合、$O(NM)$ の計算量を要します。反復比較の重複を排除し、線形時間へ改善するための基礎的な手法がKMP（Knuth-M ...
7月30日 22:26 投稿
2025牛客暑期多校訓練キャンプ第1回 解説
G. Symmetry Intervals
文字列 $S$ と $q$ 個のクエリが与えられる。各クエリでは文字列 $T$、整数 $a$、および区間 $[l, r]$（ただし実装上は $T$ 全体を対象）が与えられ、$S_{a+x-1} = T_x$ がすべての $x \in [l, r]$ で成り立つような連続部分区間の個数を求める。
アプローチとしては、$T$ の各位置 $j$ に対して対応する $S$ のインデックス $ps = j + a - 1$ を計 ...
5月16日 19:59 投稿