Longest Palindromic Substring - 字元串中最長的回文字段

需求：Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

如果一個字元串從左向右寫和從右向左寫是一樣的,這樣的字元串就叫做palindromic string

判斷回文數，中間開花。定一個中心，向兩邊散開。這個中心是從左到右移動的。需要2個遊标。

int palindrome(String ps,int left,int right) 這個方法用來判斷回文字段，傳回字段長度

String longestPalindrome(String s) 在這裡調用palindrome方法，周遊字元串去找。周遊過程注意不要越界。

以下為Java代碼：

1 /**
 2  * @author Rust Fisher
 3  * @date 2015-9-14
 4  */
 5 public class LongestPalindromicSubstring {
 6     /**
 7      * @param s - input string
 8      * @return the Longest Palindromic Substring 
 9      */
10     public static String longestPalindrome(String s) {
11         String result = "";
12         int inputLenght = s.length();
13         int startIndex = 0;
14         int longest = 1;
15         
16         for (int i = 0; i < inputLenght; i++) {
17             int oddLen = 1,dualLen = 1, currentLen;
18             oddLen = palindrome(s, i, i);
19             if (i+1 < inputLenght) {
20                 dualLen = palindrome(s, i, i+1);
21             }
22             currentLen = dualLen > oddLen ? dualLen : oddLen;
23             if (currentLen > longest){
24                 longest = currentLen;
25                 if (longest%2 == 0) {
26                     startIndex = i - longest/2 + 1;
27                 } else {
28                     startIndex = i - longest/2;
29                 }
30             }
31         }
32         for (int i = startIndex; i < startIndex+longest; i++) {
33             result += s.charAt(i);
34         }
35         return result;
36     }
37     /**
38      * @param ps - input string
39      * @param left - index move left
40      * @param right - index move right
41      * @return the current length of palindrome
42      */
43     public static int palindrome(String ps,int left,int right){
44         int thislen = 0;
45         int len = ps.length();
46         while(left >= 0 && right < len && ps.charAt(left) == ps.charAt(right)){
47             left--;
48             right++;
49         }
50         thislen = right - left - 1;
51         return thislen;
52     }
53     public static void main(String args[]){
54         System.out.println(longestPalindrome("hfiwafhaabbaaccddio128213"));
55         System.out.println(longestPalindrome("abcdefgfedcba"));
56         System.out.println(longestPalindrome("abc"));
57     }
58 }      

輸出：

aabbaa

abcdefgfedcba

a