/*
@Copyright:LintCode
@Author: Monster__li
@Problem: http://www.lintcode.com/problem/longest-palindromic-substring
@Language: Java
@Datetime: 17-03-07 15:38
*/
public class Solution {
/**
* @param s input string
* @return the longest palindromic substring
*/
public String longestPalindrome(String s) {
int s_length=s.length();
int index_front=0,index_back=1,palindrome_length;//index_back=index_front+palindrome_length-1;
int i,palindrome_length_max=1;
int max_index_front=0,max_index_back=0;
int palindromelength[][]=new int[s_length+2][s_length+2];
for(index_front=0; index_front<s_length; ++index_front)
palindromelength[index_front][1] = 1;
for(palindrome_length=2;palindrome_length<=s_length;palindrome_length++)
{
for(index_front=0;index_front<s_length&&(index_back=index_front+palindrome_length-1)<s_length;++index_front)
{
if(s.charAt(index_front)==s.charAt(index_back)&&palindromelength[index_front+1][palindrome_length-2]==palindrome_length-2)
palindromelength[index_front][palindrome_length]=palindromelength[index_front+1][palindrome_length-2]+2;
else
palindromelength[index_front][palindrome_length]=Math.max(palindromelength[index_front+1][palindrome_length], palindromelength[index_front+1][palindrome_length-1]);
if(palindrome_length_max<palindromelength[index_front][palindrome_length])
{
palindrome_length_max=palindromelength[index_front][palindrome_length];
max_index_front=index_front;
max_index_back=index_back;
}
}
}
return s.substring(max_index_front, max_index_back+1);
}
}