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.

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 "";	}

/**	 * 	 * 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);	}

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);	}

// ^ 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);	}