manacher
马拉车通过在每个字符间插入一个特殊字符，使得字符串长度为奇数，从而保证每个字符都有中心。在每个中心记录回文串的长度。
马拉车的扩展方式和\(Z\)函数类似。都是通过映射之前已经算过的位置，然后尽可能的向右扩展。复杂度\(O(n)\)
通常马拉车的题目统计回文串需要与其他数据结构结合，如线段树，树状数组等。需要一定的基本功。
void manacher(char* str,int n) {
int ans = 0, t = 0;
for (int i = 1; i <= n; ++i) {
if (t + f[t] >= i)f[i] = min(f[t - (i - t)], t + f[t] - i);
while (i - f[i] - 1 > 0 && i + f[i] + 1 <= n && str[i - f[i] - 1] == str[i + f[i] + 1])f[i]++;
if (f[i] + i > f[t] + t)t = i;
ans = max(ans, f[i]);
}
printf("%d", ans);
}
CF:30 E. Tricky and Clever Password
回文树
回文树分为奇根和偶根，偶根的 \(fail\) 指针指向奇根，而我们并不关心奇根的 \(fail\) 指针，因为奇根不可能失配。
回文树不再考虑回文中心，是以右边界为这个回文串的终点。\(fail\) 指针指向的这个右边界更短的回文串。
回文树的构建与SAM类似，找上一个回文，依次遍历\(fail\)找对应相同的字符的位置向右扩展即可。
struct PAM {
int siz, tot, lst; //siz回文树大小，tot字符串处理到第几个
int cnt[MAXN], ch[MAXN][26], len[MAXN], fail[MAXN];
char s[MAXN];
PAM() { clear(); }
int node(int l) { // 建立一个新节点，长度为 l
siz++;
memset(ch[siz], 0, sizeof(ch[siz]));
len[siz] = l;
fail[siz] = cnt[siz] = 0;
return siz;
}
void clear() {
siz = -1;
lst = 0;
s[tot = 0] = '$';
node(0);
node(-1);
fail[0] = 1;
}
int getfail(int x) { // 找后缀回文
while (s[tot - len[x] - 1] ^ s[tot])x = fail[x];
return x;
}
void insert(char c) {
s[++tot] = c;
int cur = getfail(lst);
if (!ch[cur][c - 'a']) {
int x = node(len[cur] + 2);
fail[x] = ch[getfail(fail[cur])][c - 'a']; //没有儿子默认指向偶根，偶根一直指向奇根
ch[cur][c - 'a'] = x;
}
lst = ch[cur][c - 'a'];
cnt[lst]++;
}
};
最小回文划分
考虑\(dp[i]\)是\(s\)的前\(i\)位的最小划分数。考虑转移。
\[dp[i] = \underset{s[j+1,i]为回文串}{min} dp[j] + 1 \]考虑回文串\(t\)是回文串\(s\)的后缀，那么\(t\)就是\(s\)的\(border\)。这是充分必要的。我们在kmp中有介绍\(border\)的性质。我们可以把\(s\)分为\(log|s|\)段，每一段的\(border\)都是等差数列。有了这个性质我们考虑优化dp。
优化
-
\(diff[u]\)代表\(u\)和\(fail[u]\)所代表的回文串长度差。
-
\(slink[u]\)代表这个\(border\)等差数列的最前面的位置。即第一个$diff[v] \neq diff[u] $
-
\(g[u]\)是这个\(border\)等差数列的长度对应的\(dp\)最小值。
复杂度\(O(nlogn)\)
for (int i = 1; i <= n; ++i) {
p.insert(s[i]);
for (int x = p.lst; x > 1; x = p.slink[x]) {
g[x] = dp[i - p.len[p.slink[x]] - p.dif[x]];
if (p.dif[x] == p.dif[p.fail[x]])g[x] = min(g[x], g[p.fail[x]]);
dp[i] = min(dp[i], g[x] + 1);
}
}
双倍回文
寻找最长的\(ww^Rww^R\)形式字符串。
- 维护一个\(trans\)小于等于当前节点长度一半的最长回文后缀，和\(fail\)求法类似。即可。
例题：
luogu: P5496 【模板】回文自动机（PAM）
其他方式处理回文
哈希、SA、SAM都可以用，思路都是把原串翻转。求这部分和反转后的这部分是否一致。
哈希可以快速判断某子串是否是回文串。SA和SAM考虑两个串匹配的长度和对应的位置差距可以判断是否为回文串。
标签：ch,int,manacher,回文结构,siz,fail,PAM,dp,回文 From： https://www.cnblogs.com/Qing17/p/18319756