马拉车算法用于寻找字符串中的最长回文子串。
java
class ManacherAlgo {
String longestPalindrome(String s) {
// 填充
String newS = fillStr(s);
// center是中心,right是中心的最远覆盖范围,max_center是最长回文字串的中心
int right = 0, center = 0, max_center = 0;
// 记录每个位置的最远覆盖范围
int[] radius = new int[newS.length()];
int lenOfNewS = newS.length();
// 算法主体
for (int idx = 1; idx < lenOfNewS; idx++) {
if (idx < right) {
int mirror = 2 * center - idx;
radius[idx] = Math.min(right - idx, radius[mirror]);
} else
radius[idx] = 1;
while (
(idx + radius[idx] < lenOfNewS) &&
(idx - radius[idx] >= 0) &&
(newS.charAt(idx + radius[idx]) == newS.charAt(idx - radius[idx]))
)
radius[idx]++;
if (idx + radius[idx] > right) {
right = idx + radius[idx];
center = idx;
}
if (radius[idx] > radius[max_center]) {
max_center = idx;
}
}
// 返回最长回文字串
int l = max_center - radius[max_center];
int r = max_center + radius[max_center];
return s.substring((l + 1) / 2, r / 2);
}
// 填充
private String fillStr(String s) {
StringBuilder retS = new StringBuilder("#");
for (int i = 0; i < s.length(); i++) {
retS.append(s.charAt(i)).append("#");
}
return retS.toString();
}
// 测试
public void testing() {
System.out.println(longestPalindrome("abababbb"));
System.out.println(longestPalindrome("aba"));
System.out.println(longestPalindrome("aa"));
}
}
public class manacher {
public static void main(String[] args) {
// 生成实例
ManacherAlgo obj = new ManacherAlgo();
// 测试
obj.testing();
}
}
python
# coding=utf-8
"""
author:shayue
2019/09/18
"""
class Manacher():
"""
算法步骤:
1. 输入要操作的字符串后,先进行填充,这一步的目的是为了无视奇偶差异,填补后的字符串长度必为奇数;
2. 从左往右遍历,以位置center为中心,往两边扩散,记录最大回文子串的半径,比如12321,其半径为3,将半径放入列表radius中;
3. 利用先前已经保存的半径信息,可以加快后序位置所对应回文子串的半径求解,具体实现见longest_palindromic_substring。
"""
def __init__(self, inputStr):
self.str_ = inputStr
self.right = 0
self.center = 0 #
self.radius = None # 列表
# 下面两个变量是为了找到最长子串
self.MaxPi = 0
self.Max_Pi_center = 0
def longest_palindromic_substring(self):
"""
马拉车算法,找到最大回文子串并返回
:return: str
"""
filled_s = self.fill_to_s()
self.P = [0] * len(filled_s)
print(filled_s)
for idx in range(1, len(filled_s)):
if idx < self.right:
mirror = self.get_mirror(idx)
self.P[idx] = min(self.right - idx, self.P[mirror])
else:
self.P[idx] = 1
while idx - self.P[idx] >= 0 and \
idx + self.P[idx] < len(filled_s) and \
filled_s[idx - self.P[idx]] == filled_s[idx + self.P[idx]]:
self.P[idx] += 1
if self.P[idx] + idx > self.right:
self.right = self.P[idx] + idx
self.center = idx
if self.P[idx] > self.MaxPi:
self.MaxPi = self.P[idx]
self.Max_Pi_center = idx
l = self.Max_Pi_center - self.MaxPi
r = self.Max_Pi_center + self.MaxPi
return self.str_[(l+1) // 2: r // 2]
def get_mirror(self, i):
"""
以self.center为中心,返回位置i对应到左边的位置mirror
:param i: 位置i,在self.center右边
:return: 位置mirror,在self.center左边
"""
return 2 * self.center - i
def fill_to_s(self):
"""
对self.s进行'#'填充,填充完后的字符串总长为奇数,以便算法对奇偶情况都适用
:return: str
"""
retStr = "#" + "#".join(self.str_) + '#'
return retStr
if __name__ == '__main__':
manacher = Manacher('abcababacab')
print(manacher.longest_palindromic_substring())
print(manacher.P)