我是靠谱客的博主 自然小蚂蚁,这篇文章主要介绍Java实现最长回文串,现在分享给大家,希望可以做个参考。

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

2 解决方案
2.1 中心扩展法

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

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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); } }

运行结果:

复制代码
1
2
3
4
5
6
7
8
9
10
请输入一个字符串: abba 输入目标字符串中最长回文串的长度为:4 请输入一个字符串: aabbbbba 输入目标字符串中最长回文串的长度为:7 请输入一个字符串: 我爱爱我我我啊 输入目标字符串中最长回文串的长度为:4

2.2 Manacher算法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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); } }

运行结果:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
abba abba 最长字符串长度:4 12321 最长字符串长度:5 我爱你爱我 我爱你爱我 最长字符串长度:5 我爱她 我 最长字符串长度:1

最后

以上就是自然小蚂蚁最近收集整理的关于Java实现最长回文串的全部内容,更多相关Java实现最长回文串内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(221)

评论列表共有 0 条评论

立即
投稿
返回
顶部