算法提升之字符串回文处理-（manacher）
今天给大家分享的就是关于manacher算法的解题方法与思路。
先明确几个关键变量的含义
t数组：经过预处理的字符串（插入#和边界符），长度为2n+3（n是原字符串s的长度），用于统一处理奇、偶长度的回文。res：从t数组两端开始，连续对称的最大长度（即最长的等长前缀和后缀对称部分，对应原字符串中res//2个字符，因为t数组有#分隔）。p[i]：Manacher 算法计算的回文半径数组，p[i]表示以t[i]为中心的最长回文串向左右扩展的长度（原字符串中回文长度为p[i]-1）。i：当前遍历的t数组的索引（范围1~2n+1）。
第一题：
问题描述
给定一个字符串 S ，请找出 S 的一个前缀和后缀，使得它们拼接后是一个回文串。
请输出这个串的最长长度。
输入描述
输入一行包含一个字符串 S ，由小写英文字母组成。
输出描述
输出一行包含一个整数表示答案。
输入案例：
aababa输出案例：
7代码部分：
//所求的串由两部分组成：
//1.等长的前后缀拼成的回文串
//2.原串内部的回文串
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+40;
char s[N],t[N];
int p[N];
int main()
{cin>>s+1;int n=strlen(s+1);t[0]='^',t[2*n+2]='$';for(int i=1;i<=2*n+1;++i)t[i]=i&1?'#':s[i/2];//求等长前后缀拼成的回文串的最大长度int res=0;for(int i=1;i<=2*n+1&&t[i]==t[2*n+2-i];++i)res++;//manache算法求内部回文串最大长度int c=0,r=0;for(int i=1;i<=2*n+1;++i){p[i]=i<r?min(r-i,p[2*c-i]):1;while(t[i+p[i]]==t[i-p[i]])p[i]++;if(i+p[i]>r)c=i,r=i+p[i];}//枚举内部回文串，更新答案int ans=0;for(int i=1;i<=2*n+1;++i){if(res+p[i]>=i)ans=max(ans,i-1);if(res+p[i]>=2*n+2-i)ans=max(ans,2*n+1-i);}cout<<ans<<'\n';return 0;
}注意点⚠️：
1.res的作用：
设s = "abddca"（n=6），预处理后的t数组（插入#和边界符）为：
t = ^ # a # b # d # d # c # a # $
索引：0 1 2 3 4 5 6 7 8 9 10 11 12 13
其中，t的有效长度为2*n+1=13（索引 1~13），对称位置为i和2*n+2 - i = 14 - i。
循环过程：
i=1：t[1] = '#'，t[13] = '#'→ 相等，res=1；i=2：t[2] = 'a'，t[12] = 'a'→ 相等，res=2；i=3：t[3] = '#'，t[11] = '#'→ 相等，res=3；i=4：t[4] = 'b'，t[10] = 'c'→ 不相等，循环停止。
最终res=3。
2.
1. 第一种情况：if(res + p[i] >= i) ans = max(ans, i-1)
含义：判断 “左侧等长对称前缀” 与 “以
i为中心的内部回文串” 能否拼接成回文串，并计算其长度。拆解：
res：左侧等长对称前缀的长度（从t[1]到t[res]）。p[i]：以i为中心的内部回文串向左扩展的最大长度（覆盖范围[i-p[i]+1, i+p[i]-1]）。res + p[i] >= i：表示左侧等长对称前缀（res）与内部回文串的左扩展部分（p[i]）能够 “衔接” 起来，覆盖到i的位置（即两者可以拼接成连续的回文）。i-1：此时拼接后的回文串在t数组中的长度（转换为原字符串长度时需除 2，但这里ans直接存储t数组中的有效长度，最终输出时已对应原字符串长度）。
举例：
若res=3（左侧前 3 个字符对称），i=5，p[i]=3（内部回文向左扩展 3 个单位），则res + p[i] = 6 >= 5，说明左侧对称前缀与内部回文可以衔接，拼接后的回文长度为i-1=4（对应原字符串长度 2）。
2. 第二种情况：if(res + p[i] >= 2*n+2 - i) ans = max(ans, 2*n+1 -i)
含义：判断 “右侧等长对称后缀” 与 “以
i为中心的内部回文串” 能否拼接成回文串，并计算其长度。拆解：
2*n+2 - i：t数组中i对应的右侧对称位置（例如i=2，n=3时，对称位置为2*3+2 -2=6）。res + p[i] >= 2*n+2 -i：表示右侧等长对称后缀（res）与内部回文串的右扩展部分（p[i]）能够 “衔接” 起来，覆盖到右侧对称位置（即两者可以拼接成连续的回文）。2*n+1 -i：此时拼接后的回文串在t数组中的长度（同样对应原字符串长度）。
举例：
若res=3（右侧后 3 个字符对称），i=5，p[i]=3（内部回文向右扩展 3 个单位），右侧对称位置为2*3+2 -5=3，则res + p[i] = 6 >= 3，说明右侧对称后缀与内部回文可以衔接，拼接后的回文长度为2*3+1 -5=2（对应原字符串长度 1）。
为什么这样计算能得到最长回文串？
- 回文的对称性：回文串的核心是左右对称，
res提供了 “天然对称” 的前缀和后缀基础，而p[i]提供了内部的对称部分。 - 拼接逻辑：当 “外部对称部分”（
res）与 “内部对称部分”（p[i]）能够衔接时，两者拼接后形成的整体必然也是对称的（即回文串）。 - 遍历所有可能：通过遍历
t数组的每个位置i，覆盖了所有可能的内部回文中心，确保不会遗漏最长的拼接回文串。
3.res+p[i]>=i的理解：
res + p[i] >= i 的本质：覆盖左侧边界
这个条件的核心是判断：左侧的 “等长对称前缀”（长度 res）与 “以 i 为中心的内部回文串”（半径 p[i]）能否拼接起来，覆盖到 i 这个位置。
拆解如下：
res的意义：res是从t数组最左侧（t[1]）开始，连续与右侧对称位置匹配的长度。例如res=3表示t[1]、t[2]、t[3]分别与右侧对称位置的字符相等。
它代表了字符串最左侧的 “天然对称部分”，可以直接作为回文串的左半部分。p[i]的意义：p[i]是以i为中心的最长回文串的半径（向左右扩展的长度）。例如p[i]=4表示以i为中心，向左扩展 3 个位置、向右扩展 3 个位置的子串是回文（总长度2*4-1=7）。
它代表了字符串内部的一个回文子串。res + p[i] >= i的逻辑：i是内部回文串的中心位置，i左侧的区域需要被覆盖才能形成完整回文。res覆盖了从左侧起点（t[1]）到t[res]的范围。p[i]覆盖了从i-p[i]+1到i的范围（内部回文串的左半部分）。- 当
res + p[i] >= i时，说明左侧的res区域与内部回文的左半部分（p[i]）能够 “无缝衔接”，覆盖到中心i，此时两者拼接后可以形成一个更长的回文串。
第二题：
题目描述
小蓝有一个只包含 0 和 1 字符串，请你帮他算算这个字符串有多少个子串将 00 和 11 取反后，再将整个子串反过来和原子串一样。
输入描述
输入第一行包含一个整数 n(n≤5×105)，表示字符串长度。
第二行包含一个长度为 n 的字符串 S，S 只拥有 0、1 两种字符。
输出描述
输出仅一行，包含一个整数，表示答案。
输入案例：
6
100100输出案例：
3代码部分：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=131;
const int N=5e5+10;
long long ans;
char s1[N],s2[N];
int n;
ll h1[N],h2[N],p[N];
ll get(ll h[],int l,int r){return h[r]-h[l-1]*p[r-l+1];}
int main()
{cin>>n;for(int i=1;i<=n;i++){char t;cin>>t;s1[i]=t;s2[i]=(t=='1'?'0':'1');}reverse(s2+1,s2+n+1);p[0]=1;for(int i=1;i<=n;i++){p[i]=p[i-1]*P;h1[i]=h1[i-1]*P+s1[i];h2[i]=h2[i-1]*P+s2[i];}for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){if(get(h1,i,j)==get(h2,n-j+1,n-i+1))ans++;}}cout<<ans;return 0;
}这是用的hash的算法思想，注意的是用reverse来求h2，最后get（h2，n-j+1,n-i+1）这里也要取反⚠️
接下来还有一种用manacher的思路解决的方法：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define ls o << 1
#define rs o << 1 | 1
// #define mid ((st + ed) >> 1)
typedef double db;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int base = 131;
const int mod = 998244353;
const int maxn = 5e5 + 5;
int lowbit(int x) { return x & (-x); };
int s[maxn], n, p[maxn];
void solve()
{//freopen("date.in", "r", stdin);//freopen("date1.out", "w", stdout);cin >> n;string tmp;cin >> tmp;for (int i = 1; i <= n; i++)s[i] = ((tmp[i - 1] - '0') ? 1 : -1);s[0] = 2, s[2 * n + 2] = 3;for (int i = 2 * n + 1; i >= 1; i--){if (i & 1)s[i] = 0;elses[i] = s[i >> 1];}int c = 0, r = 0;for (int i = 1; i <= 2 * n + 1; i += 2){p[i] = i < r ? min(r - i, p[2 * c - i]) : 1;while (s[i + p[i]] == -s[i - p[i]])p[i]++;if (i + p[i] > r)c = i, r = i + p[i];}int ans = 0;for (int i = 1; i <= 2 * n + 1; i += 2){int len = p[i] - 1;ans += len / 2;}cout << ans;
}
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1;// cin >> _;while (_--)solve();return 0;
}这题是马拉车算法的变体，我们知道马拉车算法的原理就是根据了回文串中最小回文半径优化的时间复杂度，例如abacabac，这段字符串，以c为回文中心，左边的b回文半径为2，则右边的b回文半径至少为2（根据对称性），然后通过暴力向右查找有没有更大的回文半径。那么这题能否借鉴这个思路？
显然是可以的，比如010101，我们定义合法串为关于中心对称的两数字必须为一个0和一个1（注：合法串并非全答案，答案的合法串中心为空，后面会解决这个问题）。则再看这个0101串，提取出合法串0101001010，以第二个0为回文中心左边为01，右边与之对应为1010，可以看到这两个都是合法串，右边合法串的长度是不是至少为2？显然是的,因为右边的串是由左边的串反转得来的，左边的串合法，右边一定合法。
那么像马拉车算法一样，为了更好的表示回文半径，我们把合法串的定义改一改，关于中心对称的左右两个数相加等于0，我们把1不动，0改为−1，−1和1中间补0，是不是就是完完全全变成马拉车算法的板子了？并且，由于我们需要合法串的长度一定为偶数，意思就是我们不能以1或是−1为中心，所以遇到他们直接跳过，只判断0为中心即可，并且以0合法半径一定为奇数。得到合法半径r，原合法01串长度为r−1，其中包含了2r−1个合法字串，把他们累加起来即可。
时间复杂度O(n)
好了今天的分享就到这里，希望对大家能有所帮助，希望大家多多关注。