回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。
输入
输入Str（Str的长度 <= 100000)
输出
输出最长回文子串的长度L。
输入样例
daabaac
输出样例
5
知乎上 https://www.zhihu.com/question/37289584 ”c加加编程思想“ 答主的回答很棒。
思路：
简要阐述一下：
对照manacher的核心代码，其实就三部分，第一部分判断C与i的关系并进行状态转移，第二部分中心扩展（暴力！），第三部分维护C。
C是啥？转移啥？？请看下文
C = max{f[id] + id}，代表算出来的回文串的最大拓展范围。
n2到 n，中间需要利用已经算出来的信息，由此得出的马拉车算法，可以看做是动态规划。
将字符串翻倍后，定义f[j]为以j为中心的回文子串长度的一半。
按照dp思想，我们要计算的是f[i]，需要用到以前算过f[j]，并且计算f[j]的时候也要遵循同样的规则。
假设维护一个最大的值C，C = f[id] + id。再设j = 2 *id - i，代表j和i中心对称。f[i]和f[j]有一个转移关系，这就是我们需要找的子状态。
C > i时。
1 、假设i + f[j] ≤ C，那么意味着 j 对应的回文子串，i也一定对应着。
此时 f[i] = f[j]。
2、否则，我们最多只能算到C - i这么多,其他的部分只能暴力比较了。
那么取个min就好了。
C ≤ i，对称过去的 j 与 i 之前没有状态关系，那就只能暴力拓展啦。
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 2e5 + 7;
char s1[maxn],s2[maxn];
int f[maxn];int manacher(int len)
{int ans = 0,id = 1,mx = 0;for(int i = 1;i < len;i++){if(id + mx > i)f[i] = min(f[id * 2 - i],id + mx - i);while(i - f[i] - 1 >= 1 && i + f[i] + 1 <= len && s2[i - f[i] - 1] == s2[i + f[i] + 1])f[i]++;if(id + mx < i + f[i]){id = i;mx = f[i];}ans = max(ans,f[i]);}return ans;
}int main()
{scanf("%s",s1 + 1);int len = (int)strlen(s1 + 1);int len2 = 0;for(int i = 1;i <= len;i++){s2[++len2] = '#';s2[++len2] = s1[i];}s2[++len2] = '#';printf("%d\n",manacher(len2));return 0;
}再补上一个字符串哈希的算法
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef unsigned long long ull;
const int maxn = 2e5 + 7;
const int mod = 29;int p[maxn],hash_l[maxn],hash_r[maxn];
char tmp[maxn],s[maxn];void get_hash(int len)
{p[0] = 1;for(int i = 1;i <= len;i++)p[i] = p[i - 1] * mod;for(int i = 1;i <= len;i++)hash_l[i] = hash_l[i - 1] * mod + s[i];for(int i = len;i >= 1;i--)hash_r[i] = hash_r[i + 1] * mod + s[i];
}bool check(int i,int mid)
{int l = hash_l[i - 1] - hash_l[i - mid - 1] * p[mid];int r = hash_r[i + 1] - hash_r[i + mid + 1] * p[mid];if(l == r)return true;return false;
}int main()
{scanf("%s",tmp + 1);int len = (int)strlen(tmp + 1);int len2 = 0;for(int i = 1;i <= len;i++){s[++len2] = '#';s[++len2] = tmp[i];}s[++len2] = '#';get_hash(len2);int ans = 0;for(int i = 1;i <= len2;i++){int l = 0,r = 0;if(i - 1 < len2 - i)r = i - 1;else r = len2 - i;int ans_t = 0;while(l <= r){int mid = (l + r) >> 1;if(check(i,mid)){ans_t = mid;l = mid + 1;}else{r = mid - 1;}}ans = max(ans,ans_t);}printf("%d\n",ans);return 0;
}