MP法
文字列 $ S が与えられたときに、各$ iについて
「文字列$ S[0,i-1\rbrackの接頭辞と接尾辞が最大何文字一致しているか」（最長borderの長さ）
を記録した配列を $ O(|S|)で構築するアルゴリズム
検索する文字列のMP配列を作り、それを用いて効率よく文字列検索を行う。
テキスト$ Sからパターン$ TをMP法で検索するとき、計算量は
前処理：$ O(|T|)
検索：$ O(|S|)
リファレンス
最長borderではなく最長tagged borderをメモすることで前処理と計算がやや速くなる。
（$ Pのtagged border(あるいはstrict border、strong borderともいう) $ Wとは、$ Pのborder $ Wであって、かつ$ P[|W|\rbrack \neq X[0\rbrackであるものを指す。）
リファレンス
verify