package practise;
import java.util.Scanner;
public class longestPalindrome {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String inputString = scanner.nextLine();
System.out.println(longestSubPalindrome(inputString));
}
}
/**
* 输入字符串,输出其包含的字母可以构成的最长回文长度
* @param str
* @return
*/
public static int longest(String str) {
int[] count = new int[128];
for (char c:str.toCharArray()) {
count[c]++;
}
int ans = 0;
for (int v:count) {
ans = ans + v/2*2;
if (v % 2 == 1 && ans % 2 == 0) {
ans++;
}
}
return ans;
}
/**
* 输入字符串,返回最长回文子串。
* 中心扩展法,n个字符,有2n-1个对称中心,中心两侧互为镜像。
* @param s
* @return
*/
public static String longestSubPalindrome(String s) {
if (s == null || s.length() < 1) {
return "";
}
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
/**
* 从left和right向两侧扩展,返回可构成回文的最大长度
* @param s
* @param left
* @param right
* @return
*/
private static int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1; // L 和 R均多加了1,返回长度为(R-L+1)-2
}
}