Manacher(马拉车算法）
## 算法概述 - 用于对字符串中回文串相关的操作 - 如寻找最长回文串 - 时间复杂度 O(n)算法原理
-
example: str = "a film called tenet"
-
寻找最长回文串的一般解法(暴力)
对于字符串中的每一个字符 进行中心拓展
伪代码 时间复杂度O(n^2)for(int i=0;i<len;++i){ int l=r=i,tmp=-1; while(l>=0&&r<len&&str[l--]==str[r++]){ tmp+=2;}//字符串长度为奇数 ans=tmp>ans?tmp:ans; l=i,r=i+1,tmp=0; while(l>=0&&r<len&&str[l--]==str[r++]){ tmp+=2;}//字符串长度为偶数 ans=tmp>ans?tmp:ans; } -
马拉车算法流程如下
-
预处理
先在字符串开头与结尾插入两个不同的特殊字符
再在字符之间插入特殊符号
如：" ^#a# #f#i#l#m# #c#a#l#l#e#d# #t#e#n#e#t#$ "
将字符串转换为奇数长度进行统一处理,首尾不同的符号帮助边界判断 -
算法核心
在暴力的同时,最大化利用已有信息,对后续操作提供加速
流程如下 :-
以每个字符为中心进行回文半径计算
str ^ # t # e # n # e # t # $ raduis 1 2 1 2 1 6 1 2 1 2 1 location 0 1 2 3 4 5 6 7 8 9 10 11 12 -
这里raduis用于记录对应位置的回文半径
把目光放在str[6] 这里计算出半径为6 (记center=6)
可以知道指针在运算时实际已经处理到了0和10的位置 (记最前位置R=12)
一般暴力操作是以下个字符str[7]为中心继续向两端进行匹配拓展
而马拉车进行的优化就是在这里
对于str[7] 7<12 断言raduis[7]=raduis[5]=1
对于str[8] 7<12 断言raduis[8]=raduis[4]=2 -
分析
5 4 3 2 1 0 # e # t # ^ n # e # t # $ 7 8 9 10 11 12 a.由对称性str[5]str[1]和str[7]str[11]是相同的两段
当计算raduis[7]和radius[8]时我们会注意它们和
对称的raduis[5]和radius[4]“大致”相同
仔细发现str[4]的回文串部分str[5]~str[3]
是包含在str[6]的回文串部分str[1]~str[11]的
而又由str[6]位置的回文性质(a.) 可以知道str[4]的回文串部分会对应在str[8]左右
即str[5]str[3]对应到str[7]str[9]
从而可以得到raduis[8]=raduis[4]
这就是马拉车算法用到的思想 -
其他情况的考虑
刚才是对应位置的回文串部分被包含在一个大的回文串里
即str[i]的 对应位置回文半径长 raduis[2C-i] + i < R (R是已知回文串最右位置)
对于raduis[2C-i] + i >= R 我们不知道溢出的部分 是否能匹配上
但可以知道至少有str[i]~ str[R]这一部分是对称的
也就是说raduis[i]数值上至少等于R - i
于是我们可以直接从溢出部分开始进行字符串比较 -
综合考虑
当正在计算的位置 i < R 的时候可以优化
raduis[2C-i] < R - i 的时候 raduis[i] = raduis[2C-i]
raduis[2*C-i] >= R - i 则raduis[i] = R - i 再从最远端位置R继续匹配 -
关于回文串返回
str ^ # t # e # n # e # t # $ raduis 1 2 1 2 1 6 1 2 1 2 1 location 0 1 2 3 4 5 6 7 8 9 10 11 12 -
原回文串的长度 len = raduis[i] - 1
这里不是巧合
raduis[i]*2-1得到预处理后的回文串长度 总是奇数
对应的回文串只有两种形式- #x#x# 原回文串长度为偶数
- #x#x#x# 原回文串长度为奇数
但不管如何'#'的个数总是比处理字符多1
(raduis[i] * 2 - 1 - 1) / 2得到正确长度 -
原回文串开始位置(包含) start = (i - raduis[i]) / 2
index/2得到原字符串位置+1的地方
i-radius[i]得到预处理串开始位置(不包含)
(i-radius[i])/2 得到原字符串开始位置(包含)
-
-
代码实现
class solution {
String manacher(String s) {
if (s.isEmpty()) {
return "";
}
StringBuilder builder = new StringBuilder("^#");
for (char c : s) {
builder.append('c');
builder.append('#');
}
builder.append('$');
char[] str = builder.toString().toCharArray();
int len = str.length;
int[] raduis = new int[len];
int C = -1, R = -1;
int ans = 0;
for (int i = 1; i < len - 1; ++i) {
raduis[i] = i > R ? 1 : Math.max(R - i, raduis[2 * C - i]);
while (str[i - raduis[i]] == str[i + raduis[i]]) {
++raduis[i];
}
if (raduis[i] > raduis[ans]) {
ans = i;
}
if (i + raduis[i] > R) {
R = i + raduis[i];
C = i;
}
}
int len = raduis[ans] - 1;
int start = (ans - raduis[ans]) / 2;
return s.subString(start, start + len);
}
}