最长回文串问题
manacher算法是用来求解最长回文串的问题。最长回文串的解法一般有暴力法、动态规划、中心扩展法和manacher算法。
- 暴力法的时间复杂度为\(O(n^3)\)，一般都会超时；
- 动态规划的时间复杂度和空间复杂度均为\(O(n^2)\)，通过矩阵压缩存储，空间复杂度常数可以降低为0.5，但时间复杂度较高，基本不能再优化；
- 中心扩展法在性能上优于动态规划，空间复杂度为\(O(1)\)，但时间复杂度仍然是\(O(n^2)\)；
- manacher性能最好，时间复杂度和空间复杂度均为\(O(n)\)
对中心扩展法的分析
//中心扩展法的代码
class Solution {
public:
string longestPalindrome(string s) {
if(s.size() == 0)return "";
int maxlen = 1, start = 0;
for(int i = 0; i < s.size(); ++i){
int len1 = expand(s, i, i);
int len2 = expand(s, i, i + 1);
int len = max(len1, len2);
if(len > maxlen){
start = i - (len - 1) / 2;
maxlen = len;
}
}
return s.substr(start, maxlen);
}
private : int expand(const string &s, int l, int r){
while(l >= 0 && r < s.size() && s[l] == s[r]){
l--;
r++;
}
return r - l - 1;
}
};
中心扩展法造成时间复杂度高的原因主要有两个方面：
- 需要分奇数和偶数两种情况讨论；
- 子串包含重复计算；
第一点从代码可以看出，第二点见插图：
对第 \(j\)个字符进行中心扩展时， 子串\(s[0, j – 1]\)都已经进行了中心扩展，以每个字符为中心的回文串信息都已经获得，在这些回文串中必然存在一个最长的回文串\(s[mx, my]\)，其对称中心记作\(id\)。如果\(j < my\)，则\(j\)一定有一个对称位置\(i\)，假设以\(i\)为中心的回文串为左侧绿色的子串，则以\(j\)为中心的绿色子串一定也是回文串。但是中心扩展法忽略了这点，对这部分子串进行了重复比对。
manacher算法思想
manacher算法主要是对中心扩展法的两方面不足进行改进。
字符串预处理
为了不区分奇数和偶数两种情况，manacher对字符串进行了预处理，在长度为\(n\)的字符串的空隙中填入\(n+1\)相同的字符，使字符串的总长度变为\(2n + 1\)。
例如：
对于字符串
abbac，处理之后为#a#b#b#a#c#（假设插入的字符为#）
处理之后的字符串与原字符串的映射关系为：\(s[i] = temps[2 * i + 1]\)
\(i\)号位置之前有 \(i+1\)个gap
处理后的最大回文串长度与原来的长度的关系：\((tempLmax – 1) / 2 = lmax\)
算法实现
-
数据结构
-
回文半径数组\(radius[len]\)
\(radius[i] = (tempLmax(i) – 1) / 2\)，含义为字符\(temps[i]\)右侧的字符个数(不懂网上很多版本为什么带上\(temps[i]\))
-
最大覆盖范围\((id, mx)\)，\(id\)为对称中心
-
-
算法实现
- 每次在进行中心扩展时，先计算一个合适的扩展起点，而不是直接从当前位置直接扩展
- 扩展的方法同中心扩展法相同
- 每次扩展完毕，要更新最大覆盖范围\((id, mx)\)和最大长度
代码
string longestPalindrome(string s) {
if(s.size() == 0)return "";
string temps = "#";
for(int i = 0; i < s.size(); ++i){
temps += s[i];
temps += '#';
}
int len = temps.size();
int radius[len] = {0};
int id = 0, mx = 0;
int start = 0, maxlen = 0;
for(int i = 1; i < len; ++i){
if(i < mx){
radius[i] = min(radius[2 * id - i], mx - i);
}
for(int dl = radius[i] + 1; i - dl >= 0 && i + dl < len; ++dl){
if(temps[i - dl] == temps[i + dl])radius[i]++;
else break;
}
if(radius[i] + i > mx){
id = i;
mx = radius[i] + i;
}
if(radius[i] > maxlen){
start = (i - radius[i]) / 2;
maxlen = radius[i];
}
}
return s.substr(start, maxlen);
}
