假设从左往右写的字符串和从右往左写的字符串相同。 这样的字符串称为palindromic string。 aba，或者像abba一样。 主题就是这样的，输入给定的字符串。 必须输出子字符串，使子字符串成为最长的padromic字符串。
提供以下三种想法
1 .双侧比较法
以abba这样的字符串为例，在abba中，一个共享偶数字符。 第一名=倒数第一。 第2位=倒数第2位……第n位=倒数第n位
以aba这样的字符串为例，在aba中。 共享奇数个字符。 如果排除中间的字符，则第1位=倒数第1位.第n位=倒数第n位
因此，如果找到长度为len1的子列，接下来测试它是否满足。 第一位=倒数第一位。 第2位=倒数第2位……n位=倒数第n位。 也就是说，测试从头尾到中间点，字符是否一个字符一个字符相等。
publicclasslongestpalindromicsubstring1{
//*
* @param args
*/
publicstaticvoidmain (字符串[ ] args ) {
//todo自动- generated method stub
system.out.println (longest palindrome1(babcbabcbaccba )；
}
publicstaticstringlongestpalindrome1(strings )。
int maxPalinLength=0；
字符串长脉冲宽度=null；
int length=s.length (；
//check all可拆卸子字符串
for(intI=0； i length； I ) {
for(intj=I1； j length； j ) {
int len=j - i；
stringcurr=s.substring(I，j 1)；
if(ispalindrome(curr ) ) {
if(lenmaxpalinlength ) {
longestPalindrome=curr；
maxPalinLength=len；
}
}
}
}
返回长周期矩阵；
}
publicstaticbooleanispalindrome {
for(intI=0； i s.length ()- 1； I ) {
if(s.Charat(I )！=s.Charat(s.Length ) (- 1 - i ) ) ) )。
返回假；
}
}
返回真；
}
}
2 .动态规划法
dp[ i ][ j ]的值为true时，表示字符串s中下标由I到j的字符构成的子串是回文串。 那么，可以发售：
dp[ i ][ j ]=dp[ i 1][ j - 1] s[ i ]==s[ j ]。
这是常见的情况，但由于需要依赖i 1、j -1，因此可能是i 1=j -1、i 1=(j - 1 )-1。 因此，应用上述公式，必须求出基准情况。
a. i 1=j -1，即回文长度为1时，dp[ i ][ i ]=true；
b.I1=(j-1 )-1，即回文长度为2时，DP[I][I1]=) s[I]==s[I1] )。
有以上分析就可以写代码。
请注意，动态规划需要额外的o(n2 )空间。
publicclasslongestpalindromicsubstring2{
publicstaticstringlongestpalindrome2(strings )。
if(s==null ) )。
返回空值；
if(s.length(=1) ) ) ) ) ) ) )。
返回s；
int maxLen=0；
字符串长度str=null；
int length=s.length (；
int [ ] [ ] table=new int [ length ] [ length ]；
//everysingleletterispalindrome
for(intI=
0; i < length; i++) {table[i][i] = 1;
}
printTable(table);
//e.g. bcba
//two consecutive same letters are palindrome
for (int i = 0; i <= length - 2; i++) {
//System.out.println("i="+i+" "+s.charAt(i));
//System.out.println("i="+i+" "+s.charAt(i+1));
if (s.charAt(i) == s.charAt(i + 1)){
table[i][i + 1] = 1;
longestStr = s.substring(i, i + 2);
}
}
System.out.println(longestStr);
printTable(table);
//condition for calculate whole table
for (int l = 3; l <= length; l++) {
for (int i = 0; i <= length-l; i++) {
int j = i + l - 1;
if (s.charAt(i) == s.charAt(j)) {
table[i][j] = table[i + 1][j - 1];
if (table[i][j] == 1 && l > maxLen)
longestStr = s.substring(i, j + 1);
} else {
table[i][j] = 0;
}
printTable(table);
}
}
return longestStr;
}
public static void printTable(int[][] x){
for(int [] y : x){
for(int z: y){
//System.out.print(z + " ");
}
//System.out.println();
}
//System.out.println("------");
}
public static void main(String[] args) {
System.out.println(longestPalindrome2("1263625"));//babcbabcbaccba
}
}
3.中心扩展法
由于回文字符串是以中心轴对称的，所以假设我们从下标 i 出发。用2个指针向 i 的两边扩展推断是否相等，那么仅仅须要对0到
n-1的下标都做此操作，就能够求出最长的回文子串。但须要注意的是，回文字符串有奇偶对称之分，即"abcba"与"abba"2种类型。
因此须要在代码编写时都做推断。
设函数int Palindromic ( string &s, int i ,int j) 是求由下标 i 和 j 向两边扩展的回文串的长度，那么对0至n-1的下标。调用2次此函数：
int lenOdd = Palindromic( str, i, i ) 和 int gjdls = Palindromic (str , i , j )，就可以求得以i 下标为奇回文和偶回文的子串长度。
接下来以lenOdd和gjdls中的最大值与当前最大值max比較就可以。
这种方法有一个优点是时间复杂度为O(n2)，且不须要使用额外的空间。
public class LongestPalindromicSubString3 {
public static String longestPalindrome(String s) {
if (s.isEmpty()) {
return null;
}
if (s.length() == 1) {
return s;
}
String longest = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
// get longest palindrome with center of i
String tmp = helper(s, i, i);
if (tmp.length() > longest.length()) {
longest = tmp;
}
// get longest palindrome with center of i, i+1
tmp = helper(s, i, i + 1);
if (tmp.length() > longest.length()) {
longest = tmp;
}
}
return longest;
}
// Given a center, either one letter or two letter,
// Find longest palindrome
public static String helper(String s, int begin, int end) {
while (begin >= 0 && end <= s.length() - 1
&& s.charAt(begin) == s.charAt(end)) {
begin--;
end++;
}
String subS = s.substring(begin + 1, end);
return subS;
}
public static void main(String[] args) {
System.out.println(longestPalindrome("ABCCBA"));//babcbabcbaccba
}
}