Question

java 编写一个方法,找出一个字符串中最长的回文子串

编写一个方法,找出一个字符串中最长的回文子串

Answer 1

Java code
?

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

import java.util.ArrayList;

import java.util.List;

public class Palindrome {

/* 找出一个字符串中最长的回文子串

* 从字符串中第i个字符开始的所有非空回文子串的个数, 记作为Ci. 此方法的复杂度为

* O(C1 + C2 + ... + Cn)

* 当字符串中任意两个非空回文子串的起始位置不同时, C1 = C2 = ... = Cn = 1, 复杂度为O(N);

* 当字符串所有字符均为同一字符时, Ci = n - i, 此时复杂度为O(N*N);

* 在多数情况下, 此方法的复杂度远低于O(N*N).

*/

public List<String> getLongestPalindrome(String theString) {

int strLen = theString.length();

List<String> results = new ArrayList<String>(strLen);

if (strLen == 0) {

return results;

}

// 从第i个位置开始的所有回文子串的结束位置.

int[] endIndice = new int[strLen + 1];

// endIndice中有效数据的长度.

int numberOfPalindromes = 1;

// 最长回文子串的长度. 对于非空串至少可以找到长度为1的回文子串.

int maxLen = 1;

results.add(theString.substring(strLen - 1));

// 计算从第i个位置开始的所有回文子串. 这样的子串分为三种:

// 1. 在从第i+1个位置开始的回文子串的基础上, 在两端加上相同的字符;

// 2. 长度为1的回文子串;

// 3. 空串.

for (int i = strLen - 2; i >= 0; i--) {

int j = 0, k = 0;

while (j < numberOfPalindromes) {

if (theString.charAt(i) == theString.charAt(endIndice[j])) {

endIndice[k] = endIndice[j] + 1;

int newLength = endIndice[k] - i;

if (newLength >= maxLen) {

if (newLength > maxLen) {

maxLen = newLength;

results.clear();

}

results.add(theString.substring(i, endIndice[k]));

}

if (endIndice[k] < strLen) {

k++;

}

}

j++;

}

// 加入长度为1的子串

endIndice[k++] = i + 1;

if (maxLen == 1) {

results.add(theString.substring(i, i + 1));

}

// 加入空串

endIndice[k++] = i;

numberOfPalindromes = k;

}

return results;

}

public static void main(String[] args) {

Palindrome p = new Palindrome();

printList(p.getLongestPalindrome("gabcecbaefd"));

printList(p.getLongestPalindrome("bbcbaefccfg"));

printList(p.getLongestPalindrome("aaaaaaaaaaa"));

printList(p.getLongestPalindrome("abcdefghijk"));

printList(p.getLongestPalindrome("abcdeeddejk"));

printList(p.getLongestPalindrome(""));

}

public static void printList(List<? extends Object> list) {

System.out.println("**************************");

System.out.println(list.size() + " result(s):");

for (Object o : list) {

System.out.println(o);

}

}

}

Answer 2

public class test {
public static void main(String args[]) {
String s = "abaccdccabcdcba";
System.out.println(getMax(s));
}
static String getMax(String s){
char[] b = s.toCharArray();
int start = 0;
int maxLength = 0;
for(int i = 0;i<b.length;i++){
int tempLength = 0;
int tempStart = 0;
for(int j=0;j<=i&&j<b.length-i;j++){
System.out.println(b[i-j]+"==="+b[i+j]);
if(b[i-j]==b[i+j]){
tempStart = i-j;
tempLength +=2;
}else
break;
}

if(tempLength>maxLength){
start = tempStart;
maxLength= tempLength;
}
System.out.println("临时起始位置"+tempStart+":"+tempLength+"|起始位置"+start+":"+maxLength);
}

String result = s.substring(start, maxLength);
return result;
}
}额 写了个 虽然效率不高 但能实现了