简介
Manacher 算法是一种用于在线性时间内找到字符串中最长回文子串的算法。该算法的核心思想是利用回文的对称性,通过动态规划的方式避免重复计算,从而显著提高效率。下面我将详细解释这个算法,并给出一个 Java 示例。
算法详解
1. 预处理字符串
为了处理奇数长度和偶数长度的回文子串,Manacher 算法通过在每个字符之间(包括字符串首尾)插入一个特殊字符(如 #
),并在字符串首尾添加不同的特殊字符(如 ^
和 $
),从而将所有情况统一为奇数长度处理。
注意: 特殊字符 ^ 和 $ 也可以不加,算法需要特殊处理一下
2. 定义辅助数组
- 定义一个数组 p,其中 p[i] 表示 以 i 为中心的最长回文子串的半径(包括中心字符)
- 半径的定义使算法可以方便地利用回文的对称性
3.初始化
- 初始化 p 数组,并设置两个指针 c (当前回文中心) 和 r (当前回文边界)
4. 遍历字符串
- 对于每个字符
i
,计算其对应的回文半径P[i]
。 - 如果
i
在R
的左边(即i < R
),则利用对称性找到i
关于C
的对称点j = 2*C - i
。- 如果
P[j]
不超过R - i
(即对称的回文部分完全在已知的回文内部),则P[i] = P[j]
。 - 否则,需要扩展
i
的回文半径,直到遇到不匹配的字符或到达字符串边界。
- 如果
- 更新
C
和R
,如果i + P[i] > R
,则更新C = i
和R = i + P[i]
。
5. 找到最长的回文子串
- 遍历
P
数组,找到最大的P[i]
,其对应的回文子串即为原字符串中从i - P[i] / 2
到i + P[i] / 2 - 1
(去除预处理字符)的子串。
// 此处算法中没有 在开头结尾添加特殊字符。只用到分隔符 "#"
public class L5 {
public static void main(String[] args) {
L5 l5 = new L5();
String r = "babad";
String s = l5.longestPalindrome(r);
System.out.println(s);
}
public String longestPalindrome(String s) {
if (s == null || s.isEmpty()) {
return "";
}
char[] str = marcherString(s);
int[] p = new int[str.length];
marcherFind(str, p, 0);
// 找到最长回文子串
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < p.length - 1; i++) {
if (p[i] > maxLen) {
maxLen = p[i];
centerIndex = i;
}
}
// 提取原字符串中的最长回文子串
int start = (centerIndex - maxLen) / 2;
return s.substring(start, start + maxLen);
}
private void marcherFind(char[] s, int[] p, int l) {
int c = l - 1;
int r = l - 1;
int n = s.length;
for (int i = l; i < n; i++) {
p[i] = r > i ? Math.min(p[2 * c - i], r - i) : 1;
while (i + p[i] < n && i - p[i] > l - 1 && s[i + p[i]] == s[i - p[i]]) {
p[i]++;
}
p[i]--;
if (i + p[i] > r) {
r = i + p[i];
c = i;
}
}
}
private char[] marcherString(String s) {
char[] chars = s.toCharArray();
char[] ans = new char[chars.length * 2 + 1];
int index = 0;
for (int i = 0; i != ans.length; i++) {
ans[i] = (i & 1) == 0 ? '#' : chars[index++];
}
return ans;
}
}