KMP法
Knuth-Morris-Pratt-Algorithmusの略。文字列検索に使える。
接頭辞、接尾辞ってなんや…？←おい
おきもち
普通のO(|S|×|T|)のやり方では、文字列を比較していくとき、
table:example
a b c d e f g h a b c d e f g x
a b c d e f g x
でhとxが違ってた時に次を
table:example2
a b c d e f g h a b c d e f g x
a b c d e f g x
こういう風に1つずらして比較しようとする。「いや、次a出てくるのもっと後だから
table:example3
a b c d e f g h a b c d e f g x
a b c d e f g x
hの次まで飛ばしちゃってもいいんじゃないの？（b~hまではaが出てこないので）」
という風に、ミスったときに次どこから始めるかを工夫したい、というのがKMP法のおきもちらしい。
他のパターン
table:other1
a b c a b c |a| b c a b c x
a b c a b c |x|
table:other2
a b c a b c |a| b c a b c x
a b c |a| b c x
既に4,5,6文字目のabcは3文字右にずらしたところで合ってると思うから最初のabc照合すっ飛ばして7文字目から照合始めようぜ、みたいなパターン。
で、これをうまいこと計算するのに便利な配列が…ある。それをO(N)で構築しておくと、上みたいな作業がいい感じにできちゃう。
一旦今の感覚で動画を見れば、英語が分からなくてもそれなりに意味は分かる…はず？
https://www.youtube.com/watch?v=GTJr8OvyEVQ