あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

昨日の記事の続きです。 Z algorithm 文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。 例えば、 aaabaaaab 921034210 こんな感じです。Z algorithmのテクニックはManacherとよく似ています。ですので、以下の解説記事を読む前に…