概念
用hash求最长回文串/回文串数
首先，易知，回文串具有单调性。
如果字符串 $s[l...r]$ 为回文串串，那么 $s[x...y]$（$l < x, y < r$ 且 $|l-x| = |r-y|$）也一定是回文串。
因此，可以二分。
通常，枚举一下起点或者中点，然后二分长度。
这样复杂度为 $O(nlogn)$，逊色于马拉车 $O(n)$，但在时限不那么紧的情况下，hash也是不错的选择。
例题
题意：对于一个 0/1 串，如果将这个字符串 0 和 1 取反后，再将整个串反过来和原串一样，就称作「反对称」字符串。先给出一个长为 $n$ 的 0/1 串，求它有多少反对称字串。（$1 \leq n\leq 500000$）
分析：
先正向求一遍hash，再反向求一遍hash（0，1互换）。
枚举中点，判断左右两半的hash值是否相同。
显然，不存在长度为奇数的反对称串。
#include <bits/stdc++.h>
using namespace std; typedef unsigned long long ull;
typedef long long ll;
const ull base = ;
const int maxn = 5e5 + ; ull h1[maxn], h2[maxn], p[maxn];
int n;
ll ans;
char s[maxn]; ull get_h1(int l, int r)
{
return h1[r] - h1[l-]*p[r-l+];
}
ull get_h2(int l, int r)
{
return h2[l] - h2[r+]*p[r-l+];
} int check(int x)
{
int l=, r = min(x, n-x);
int ans=;
while(l <= r)
{
int mid = (l+r) >> ;
if(get_h1(x-mid+,x) == get_h2(x+, x+mid))
{
ans = mid;
l = mid + ;
}
else r = mid - ;
}
return ans;
} int main()
{
scanf("%d%s", &n, s+);
p[] = ;
for(int i = ;i <= n;i++)
{
p[i] = p[i-]*base;
h1[i] = h1[i-]*base + (ull)s[i];
}
for(int i = n;i >= ;i--) h2[i] = h2[i+]*base + (ull)(s[i] == '' ? s[i]+ : s[i]-); for(int i = ;i < n;i++) ans += check(i);
printf("%lld\n", ans);
return ;
}