马拉车算法java实现
时间: 2024-06-02 10:06:02 浏览: 23
马拉车算法是一种常用于字符串匹配的算法,其核心思想是利用回文串的对称性来减少比较次数。Java中可以通过以下步骤实现马拉车算法:
1. 预处理字符串,将字符串中的每个字符用一个特殊字符隔开,如:将字符串"abc"变成"#a#b#c#"
2. 维护一个数组P,其中P[i]表示以i为中心的最长回文子串的半径长度。具体实现时,可以使用一个中心点center和右边界right来维护,其中center表示当前已知的最长回文子串的中心点,right表示该回文子串的右边界。根据回文串的对称性,可以利用已知回文串的左侧字符的对称点来推出右侧字符的回文半径。
3. 遍历字符串,根据P数组更新center和right,并记录最长回文子串的起始位置和长度。
以下是Java代码实现示例:
```java
public class ManacherAlgorithm {
public static String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
StringBuilder sb = new StringBuilder();
sb.append("#");
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i));
sb.append("#");
}
String str = sb.toString();
int[] P = new int[str.length()];
int center = 0, right = 0;
int start = 0, maxLen = 0;
for (int i = 0; i < str.length(); i++) {
if (i < right) {
P[i] = Math.min(right - i, P[2 * center - i]);
}
while (i - P[i] - 1 >= 0 && i + P[i] + 1 < str.length()
&& str.charAt(i - P[i] - 1) == str.charAt(i + P[i] + 1)) {
P[i]++;
}
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
if (P[i] > maxLen) {
start = (i - P[i]) / 2;
maxLen = P[i];
}
}
return s.substring(start, start + maxLen);
}
public static void main(String[] args) {
String s = "babad";
System.out.println(longestPalindrome(s));
}
}
```