需求：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
