Manacher算法
1.Manacher算法解决的问题
字符串str中,最长回文子串的长度如何求解?如何做到时间复杂度O(N)完成?
回文序列是从左往右和从右往左看一样,如abba,从左往右是abba,从右往左也是abba一样。
测试用例:abc12320de1,最长回文子串为232,长度为2.
1.1一般想到的解法
以每一个位置为对称轴向两边扩展,看看以每个位置为中心能扩多大。
例如:a121b11311c
但是这个思路只能找到长度为奇数的回文,不能找到长度为偶数的回文。
例如:0110
按这种方法不能找到长度为偶数的回文0110。
1.2改善方法
可以在原始字符串左右两边和每两个字符串之间加上特殊字符。
例如:122131221
将扩完的回文长度除以2就能得到原串回文长度,这样不仅能找到奇数串回文长度也能找到偶数串回文长度。时间复杂度为O(N^2)。
2.Manacher算法
2.1回文半径、回文直径和回文半径数组
回文半径和回文直径的定义:
- 回文直径:以一个字符为中心往两边括出来整个区域的大小叫回文直径。
- 回文半径:以一个字符为中心往两边括出来一半区域的大小**(包括中心字符)**叫回文半径。
例如:#a#1#2#1#b#,以2为中心往两边扩回文直径为7,回文半径为4.
回文半径数组:从字符串左往右遍历,将每个字符的回文半径记录下来放进一个数组里就组成了一个回文半径数组。
如#a#1#2#1#b#的回文半径数组为:[1 2 1 2 1 4 1 2 1 2 1].
2.2之前扩的所有位置中所到达的最右回文右边界及中心点
名字比较拗口,举个例子:
例如:#1#2#2#1#...
$$
R = max(R, 下标 + 回文半径 - 1)
C = R ➗ 2
$$
2.3Manacher算法过程
①来到一个位置,不在最右回文边界里,暴力扩,没有优化。
②有优化:来到一个位置,在最右回文边界里,一定存在下述关系,i在中心点c和最右回文边界R中间,画出i关于c的对称点i’,根据i’的状况可以分为几个小类。
1)i’ 的回文区域∈[L,R],此时i的回文半径等于i’的回文半径。(由于逆序关系)
2)i’的回文区域超出了L的左侧,此时i的回文半径等于R-i+1
3)i’的回文区域左边界与L相同,则R’到R这一段一定是回文,但R’往左R往右的区域还需继续验证。
2.4代码
string manacherString(string str) {
string res;
int index = 0;
int size = str.size() * 2 + 1;
for (int i = 0; i != size; ++i) {
res += (i % 2 == 0) ? '#' : str[index++];
}
return res;
}
int maxLcpsLength(string s) {
if (s.size() == 0) {
return 0;
}
string str = manacherString(s);
vector<int> pArr(str.size());
int C = -1;
int R = -1;
int maxValue = INT32_MIN;
for (int i = 0; i != str.size(); ++i) {
pArr[i] = R > i ? min(pArr[2 * C - i], R - i) : 1;
while (i + pArr[i] < str.size() && i - pArr[i] > -1) {
if (str[i + pArr[i]] == str[i - pArr[i]]) {
pArr[i]++;
} else {
break;
}
}
if (i + pArr[i] > R) {
R = i + pArr[i];
C = i;
}
maxValue = max(maxValue, pArr[i]);
}
return maxValue - 1;
}
3.例题
Manacher算法精髓在于其Manacher数组,不仅可以解决最长回文子序列问题,还能用于解决更多回文序列的问题。
【例题】:给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
示例 1:
输入:s = “abc”
输出:3
解释:三个回文子串: “a”, “b”, “c”
示例 2:
输入:s = “aaa”
输出:6
解释:6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindromic-substrings
class Solution {
public:
string manacherString(string str) {
string res;
int index = 0;
int size = str.size() * 2 + 1;
for (int i = 0; i != size; ++i) {
res += (i % 2 == 0) ? '#' : str[index++];
}
return res;
}
vector<int> maxLcpsLength(string s) {
if (s.size() == 0) {
return {};
}
string str = manacherString(s);
vector<int> pArr(str.size());
int C = -1;
int R = -1;
for (int i = 0; i != str.size(); ++i) {
pArr[i] = R > i ? min(pArr[2 * C - i], R - i) : 1;
while (i + pArr[i] < str.size() && i - pArr[i] > -1) {
if (str[i + pArr[i]] == str[i - pArr[i]]) {
pArr[i]++;
} else {
break;
}
}
if (i + pArr[i] > R) {
R = i + pArr[i];
C = i;
}
}
return pArr;
}
int countSubstrings(string s) {
int res = 0;
vector<int> pArr = maxLcpsLength(s);
for (int i : pArr) {
res += i / 2;
}
return res;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)