昨日の記事の続きです。 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; } このコードが何をしているのかを見ていきます。 と
![文字列の頭良い感じの線形アルゴリズムたち2 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ](https://cdn-ak-scissors.b.st-hatena.com/image/square/3954f5488e1ee578ea91038f0779d375eade86f7/height=288;version=1;width=512/http%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fs%2Fsnuke%2F20141202%2F20141202232346.png)