又是一道明明很明晰却困了我一个上午的题。完了我刷蓝书的进度要被吊打了
解一 字符串Hash结合二分
预处理出两个字符串的前缀哈希。对于每一个的后缀，设其与的最大匹配长度为。容易发现二者前缀哈希是否相等具有单调性。二分每个后缀的答案，最后统计每种的计数即可。代码实现略。
其实昨晚扫一眼题就想到了这个做法。要不是愣是要研究KMP，也不至于沦落到如此地步（
字符串
唉，还是没有考虑清楚细节。
容易发现，一个双倍回文串必定是一个回文串，同时前半段也是一个回文串。那么在使用Manacher算法求取每个字符对应的最长回文串时，就可以同步更新答案。
但一开始我写出这样的判断：
- 1
- 2
- 3
// 完成第i个字符的最长回文的更新后 if (len[i] % 4 == 0 && len[i - (len[i] >> 1)] == len[i] / 2) ans = max (ans, len[i]);
