因为总是忘掉板子所以这里贴一下我个人对\(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];