Manachar
文字列Sについて、各i番目の文字を中心にした回文(「しんぶんし」みたいな)の最大半径をO(N)で求めちゃう。
ManacharさんのアルゴリズムなのでManacher's Algorithmとも言われる。
table:1
A B A B A B A
1 3 5 7 5 3 1
こんな感じのをO(N)で求めます
おきもち
table:2
A B A B A B A
1 3 5 7
途中まで完成してるときに、この真ん中のBを基準にして長さが7の回文になってる（左右対称になってる）から、その親回文（造語）に含まれる左右の子回文（造語）の半径も対称になるんじゃね？というのが基本となるおきもち
すぬけさんの記事のメモ…
code:そのまま実装するとこうなります.cpp
int c = 0;
for (int i = 0; i < S.size(); ++i) { // iは左からスライドするように動く
int l = c - (i-c); // l…親回文を対称にしたときのiの反対、左側の位置
if (i+Rl < c+Rc) { // 左側をそのままコピーしてもはみ出る可能性がないなら（疑問1） } else {
int j = c+Rc - i; // 少なくとも親回文の右端に当たるまでは半径が保証されている（疑問2） while (i-j >= 0 && i+j < S.size() && Si-j == Si+j) ++j; // iを基準に左右に広げる,jは半径 c = i; // 親回文の位置を更新
}
}
R[i]…i文字目を中心とした回文の半径
c…親回文の位置
R[c] 親回文の半径
疑問1. なぜ<=ではなく、<を使うのか
なんでif (i+R[l] < c+R[c])で、「<」を使っているのか（<=でよくない…？と一瞬思ってしまったので）。
→「<」が成り立つということは、子回文が親回文の内側で完結している、ということ。親回文より外の世界に飛び出していかないことが保証される。
<=で失敗する例を挙げてみる。
table:例
0 1 2 3 4 5 6 7
a b a a a b a a
1 2 1 4* 1 ?
ここで親回文の中心c=3、子回文の中心=5である。
親回文の右端はc+R[c]、つまり3+4で7（たぶん半開区間）
（コピーしたとき）子回文の右端はi+R[l]、つまり5+2で7
<=にしてしまうと「親回文に含まれているので左のコピーができる」と判断されて、2が代入されてしまう。しかし、正しくは
table:正
0 1 2 3 4 5 6 7
a b a a a b a a
1 2 1 4 1 3*
2ではなく3である(aabaa)。
親回文が重なっているのは太字部分なのに、親回文より外のやつ(7番目のa)と手を組んで半径を伸ばしてしまっている。
abaaabaa
table:<が成り立つ例
0 1 2 3 4 5 6 7
a b c a c b a a
1 1 1 4 1 1
これだと、5番目の半径が1なので6<7になる。このとき
abcacbaa
という風になっている。bが右側とつながる心配がないので、安心してコピーできる。
疑問2. jがマイナスにならない理由
c+R[c] - iがマイナスにならない理由を説明していく。
前提：c < iである（親回文の中心は子回文より左側にある）。
まず、c+R[c] - iがマイナスになると仮定する。
すると0 > c+R[c] - iよりi > c+R[c]となる。
ここで手前のif文の処理、if (i+R[l] < c+R[c])を頭に入れながら、1つ前のループの時の状態を考えてみる。
1つ前のループでした可能性のある分岐は2通りあります。
if (i+R[l] < c+R[c])がtrueで、コピーが実行されてcは変わらず
でもこれはよく考えるとありえなくて、1手後がi > c+R[c]なら（仮定より）、その1つ前の状態はi--から少なくともi >= c+R[c]になるはず（cは変わらない）。でもこれだとif文ではfalseになり矛盾する。
if (i+R[l] < c+R[c])がfalseで、cが更新された
1つ前のループでcが更新された、ということは次のターンでは$ c - i = -1 になる。ここで半径が1未満になることはなくてR[c]も必ず1以上なので、c+R[c] - iは0以上になる。これは仮定に矛盾する。
よってどちらの場合でも矛盾が発生するので、この仮定はおかしい。なので、c+R[c] - iが0以上であることが導けます。
もしもjが0だったとしても、S[i-j] == S[i+j]が絶対満たされりするので、jは後々必ず1以上になることも分かります。
半径が保証されている、とは
一歩手前のif文で、子回文がはみ出る可能性がある→子回文の右端が親回文の右端「以上」であることがわかっているので、半径が親回文の右端まで行かずに終わることはない。それだったらif文違う方に行ってるはず。