因为总是忘掉板子所以这里贴一下我个人对(manacher)的感性理解. 可能不够严谨求轻喷(QwQ)
char ch = getchar (); s[0] = s[1] = '#';
while (isalpha (ch)) {
n = n + 2;
s[n] = ch;
s[n + 1] = '#';
ch = getchar ();
}
n = n + 1;
这一部分是把原先连续的字符串拆开. 例如("abcd")这个串, 经过处理会变成("#a#b#c#d#")而便于处理. 对应的答案只要求(Expand - 1)就可以了
if (i < rt) _exp[i] = min (_exp (mid * 2 - i), rt - i);
这一句的作用是 : 利用回文串的对偶性, 处理(exp)的值. 这里(mid)和(rt)代表的是上一个较大的回文串.
while (s[i + _exp[i]] == s[i - _exp[i]]) ++_exp[i];