10182: 学习系列 —— Manacher算法
[Creator : ]
Description
【算法描述】
给定一个长度为 $n$ 的字符串。
要求在 $O(n)$ 的时间复杂度之内求出它的最长回文子串的长度。
【Solution】
首先将整个字符串中任意两个位置间插入字符 # （左右两端也要加上不同字符防止越界）。
例如原先是
设 $d_i$ 表示为以 $i$ 为中心点的最大半径（右端点到中心点的串的长度，包括两端）。
从左向右扫描每一个 $i$，
给定一个长度为 $n$ 的字符串。
要求在 $O(n)$ 的时间复杂度之内求出它的最长回文子串的长度。
【Solution】
首先将整个字符串中任意两个位置间插入字符 # （左右两端也要加上不同字符防止越界）。
例如原先是
a a b a a处理后变为
$ # a # a # b # a #这样处理使得原串中的任意回文串在后串中都表示为奇数长度串的形式，且都有一个中心点。
设 $d_i$ 表示为以 $i$ 为中心点的最大半径（右端点到中心点的串的长度，包括两端）。
从左向右扫描每一个 $i$，
- 已知 $i$ 之前的所有回文串中右端点最靠右的串的中心点 $m$ 以及右端点 $r$。
- 若 $i≤r$，设初始 $d_i=p_{2m−i}$（$2m−i$ 为 $i$ 在此串上的对称点）；否则设初始 $d_i=1$。
- 不断扩大边界，若 $s_{i−d_i}=s_{i+d_i}$ 成立，$d_i$ 加一。
- 判断 $i+d_i−1$ 是否大于 $r$，更新 $m$ 和 $r$。
数组下标 0 1 2 3 4 5 6 7 8 9 原始字符串 a a b a 处理后字符串 $ # a # a # b # a # d[i] 1 2 3 2 1 4 1 2 1
Input
【模板代码】
/*
* Manacher
* d[i]表示以 i 为中心点构成回文字符串的最大半径。
* 时间复杂度：O(n)，其中n是字符串长度
*/
std::vector<int> d;//回文半径
void manacher(const string &s){
//特别注意：s是处理好的字符串
//假设原始字符串为 abcba
//处理好的字符串为 $#a#b#c#b#a#
//字符串从下标 1 开始
int n=s.size()-1;
//重置数组z数据
d.assign(n+1,0);
d[1]=1;
for(int i=2,l,r=1; i<=n; i++){
//不管以i为对称中心的回文串的右边界是不是超过了r,
//取以l ~ r的中点为对称中心的对称点的d值和到r的最小值
if(i<=r){
d[i]=min(d[r-i+l], r-i+1);
}
while(s[i-d[i]]==s[i+d[i]]){
d[i]++;
}
// 判断一下超过r之后的字符是不是还是包含在以i为中心的回文串内
if(i+d[i]-1>r){
l=i-d[i]+1;
r=i+d[i]-1;
}
}
}