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.
https://leetcode.com/problems/longest-palindromic-substring/
求最大回文的长度，其实这道题比上一道有意思。
方法1 循环查询 （该方案为O(N*N*N)）
public static boolean isPalindrome(String s, int start, int end) {
if (((end - start) & 0x1) == 1) {
while (start + 1 != end) {
if (s.charAt(start++) != s.charAt(end--)) {
return false;
}
}
return s.charAt(start) == s.charAt(end);
} else {
while (start != end) {
if (s.charAt(start++) != s.charAt(end--)) {
return false;
}
}
}
return true;
}
public static String longestPalindrome_1(String s) {
int len = s.length();
if (len < 2) {
return s;
}
for (int i = 0, end=len/2; i < end; i++) {
for (int j = len - 1, k = i; k > -1; j--, k--) {
if (k == j && j == i) {
return "";
}
if (isPalindrome(s, k, j)) {
return s.substring(k, j + 1);
}
}
}
return "";
}
方法2 动态规划 （该方案为O(N*N)）
由于没学过动态规划，特意去学习了一下
/**
*
* 1. 初始条件：
空串 看作是回文的最初始条件，LP[i][i-1]=1。这作为初始状态，并不认为是有回文。
单字符串 是直接认为有回文的，LP[i][i]=1。
2. 状态转移：
若LP[i][j]=1且a[i-1]==a[j+1] ,那么有LP[i-1][j+1]=1,否则LP[i-1][j+1]=0
* @param s
* @return
*/
public static String longestPalindromeDP_2(String s) {
int n = s.length();
int longestBegin = 0;
int maxLen = 1;
boolean[][] table = new boolean[n][n];
// 单字符
for (int i = 0; i < n; i++) {
table[i][i] = true;
}
// 双字符
for (int i = 0; i < n - 1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
table[i][i + 1] = true;
longestBegin = i;
maxLen = 2;
}
}
// 子串长度
for (int len = 3; len <= n; len++) {
// 子串的起始位置
for (int i = 0; i < n - len + 1; i++) {
// 子串的结束位置
int j = i + len - 1;
// DP条件
if (table[i + 1][j - 1] && s.charAt(i) == s.charAt(j) ) {
table[i][j] = true;
longestBegin = i;
maxLen = len;
}
}
}
return s.substring(longestBegin, longestBegin + maxLen);
}
方法3 中心扩展，方法1的优化版本 （该方案为O(N*N)）
static class Pair {
int s;
int e;
public Pair(int s, int e) {
this.s = s;
this.e = e;
}
int length() {
return e - s + 1;
}
}
public static Pair expandAroundCenter2(String s, int c1, int c2) {
int l = c1, r = c2;
int n = s.length();
while (l > -1 && r < n && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return new Pair(l + 1, r);
}
public static String longestPalindromeSimple2(String s) {
int n = s.length();
if (n == 0)
return "";
Pair longest = new Pair(0, 1); // a single char itself is a
// palindrome
int i = 0;
// 偶回文
Pair p2 = expandAroundCenter2(s, i, i + 1);
if (p2.length() > longest.length())
longest = p2;
for (i = 1; i < n - 1; i++) {
// 奇回文
Pair p1 = expandAroundCenter2(s, i, i);
if (p1.length() > longest.length())
longest = p1;
// 偶回文
p2 = expandAroundCenter2(s, i, i + 1);
if (p2.length() > longest.length())
longest = p2;
}
return s.substring(longest.s,longest.e);
}
方法.后缀数组， logN * O(n)
方法5.Manacher算法， O(n)
// ^ and $ 避免空指针
static StringBuilder preProcess(String s) {
int n = s.length();
StringBuilder buff = new StringBuilder("^");
for (int i = 0; i < n; i++) {
buff.append("#").append(s.charAt(i));
}
buff.append("#$");
return buff;
}
public static String longestPalindrome(String s) {
if (s.length() < 2) {
return s;
}
// 插入到^#c#a#b#b#a#$
StringBuilder T = preProcess(s);
int length = T.length();
int[] p = new int[length]; //存储每一个位置的长度
int C = 0, R = 0;
for (int i = 1; i < length - 1; i++) {
int i_mirror = C - (i - C);
int diff = R - i;
// prettyPrint(T, C, R, i, i_mirror, p);
if (diff >= 0)// 当前i在C和R之间，可以利用回文的对称属性
{
// R 能移动已经判断是相等过
if (p[i_mirror] < diff)// i的对称点的回文长度在C的大回文范围内部
{
p[i] = p[i_mirror];
// System.out.println(T.charAt(i_mirror) + "<<$>>"+ T.charAt(i));
} else {
p[i] = diff;
// i处的回文可能超出C的大回文范围了
while (T.charAt(i + p[i] + 1) == T.charAt(i - p[i] - 1)) {
p[i]++;
}
C = i;
R = i + p[i];
}
} else {
p[i] = 0;
while (T.charAt(i + p[i] + 1) == T.charAt(i - p[i] - 1)) {
p[i]++;
}
C = i;
R = i + p[i];
}
}
int maxLen = 0;
int centerIndex = 0;
// 最大的索引
for (int i = 2; i < length - 1; i+=1) {
if (p[i] > maxLen) {
maxLen = p[i];
centerIndex = i;
}
}
// 计算起始地址
centerIndex = (centerIndex - 1 - maxLen) / 2;
return s.substring(centerIndex, centerIndex + maxLen);
}