文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ昨日の記事の続きです。 Manacher 文字列が与えられた時、各 i について「文字 i を中心とする最長の回文の半径」を記録した配列 R を O(|S|) で構築するアルゴリズムです。半径というのは、(全長+1)/2です。 例えば、 abaaababa 121412321 こんな感じです。 結論から言うと、Manacherのコードは以下のようになります。 int i = 0, j = 0; while (i < S.size()) { while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j; R[i] = j; int k = 1; while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k; i += k; j -= k; } このコードが何をしているのかを見ていきます。 と
