Z-Algorithm
文字列が与えられた時、各
$ i
について「
$ S
と
$ S[i:|S|-1\rbrack
の最長共通接頭辞の長さ（LCP）」を記録した配列
$ A
を
$ O(|S|)
で構築するアルゴリズム
リファレンス
文字列の頭良い感じの線形アルゴリズムたち３ / あなたは嘘つきですかと聞かれたら「YES」と答えるブログ