Java实现最长回文串

1 问题描述
给定一个字符串，求它的最长回文子串的长度。

2 解决方案
2.1 中心扩展法
此处，首先枚举出回文串的中心位置，然后，再在该位置上分别向左和向右扩展，记录并更新得到的最长回文串的长度。

package com.liuzhen.string_1;
import java.util.Scanner;
public class StringLongestPalindrome {
/*
* 参数A：给定字符串
* 函数功能：返回字符串A中最长回文串的长度
*/
public int getLongestPalindrome(String A){
char[] arrayA = A.toCharArray();
int max = 0;
int tempMax = 0;
if(A.equals("") || A.equals(null))
return 0;
for(int i = 0;i < arrayA.length;i++){
//i为回文串的中心位置
//当回文串位数为奇数时
for(int j = 0;(i-j) >= 0 && (i+j) < arrayA.length;j++){
if(arrayA[i-j] != arrayA[i+j])
break;
tempMax = 2*j + 1;
}
if(tempMax > max)
max = tempMax;
//当回文串位数为偶数时
for(int j = 0;(i-j) >= 0 && (i+j+1) < arrayA.length;j++){
if(arrayA[i-j] != arrayA[i+j+1])
break;
tempMax = 2*j + 2;
}
if(tempMax > max)
max = tempMax;
}
return max;
}
public static void main(String[] args){
StringLongestPalindrome test = new StringLongestPalindrome();
Scanner in = new Scanner(System.in);
System.out.println("请输入一个字符串：");
String A = in.nextLine();
int maxA = test.getLongestPalindrome(A);
System.out.println("输入目标字符串中最长回文串的长度为："+maxA);
}
}

运行结果：

请输入一个字符串：
abba
输入目标字符串中最长回文串的长度为：4
请输入一个字符串：
aabbbbba
输入目标字符串中最长回文串的长度为：7
请输入一个字符串：
我爱爱我我我啊
输入目标字符串中最长回文串的长度为：4

2.2 Manacher算法

package com.liuzhen.practice;
import java.util.Scanner;
public class Main {
public void Manacher(String A) {
StringBuffer s = new StringBuffer("$#");
for(int i = 0;i < A.length();i++) {
s.append(A.charAt(i));
s.append("#");
}
A = s.toString();
int[] P = new int[A.length()];
int mx = 0, id = 0;
for(int i = 1;i < A.length();i++) {
if(mx > i)
P[i] = Math.min(P[2 * id - i], mx - i);
else
P[i] = 1;
while(i + P[i] < A.length() && i - P[i] >= 0 && A.charAt(i + P[i]) == A.charAt(i - P[i])) {
P[i]++;
}
if(P[i] + i > mx) {
mx = i + P[i];
id = i;
}
}
int result = -1;
int i = 0, t = 0;
for(;i < P.length;i++) {
if(P[i] > result) {
result = P[i];
t = i;
}
}
for(int j = t - result + 1;j <= t + result - 1;j++) {
if(A.charAt(j) != '#')
System.out.print(A.charAt(j));
}
System.out.println("n最长字符串长度："+(result-1));
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
String A = in.next();
test.Manacher(A);
}
}

运行结果：

abba
abba
最长字符串长度：4
12321
最长字符串长度：5
我爱你爱我
我爱你爱我
最长字符串长度：5
我爱她
我
最长字符串长度：1

最后

以上就是自然小蚂蚁为你收集整理的Java实现最长回文串的全部内容，希望文章能够帮你解决Java实现最长回文串所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。