public String longestPalindrome(String s) {
		if (s == null || s.length() == 0) {
			return s;
		}

		char[] ss = s.toCharArray();
		int l = ss.length;
		char[] ts = new char[2 * l + 3];
		ts[0] = '^';
		for (int i = 0; i < l; i++) {
			ts[2 * i + 1] = '#';
			ts[2 * (i + 1)] = ss[i];
		}
		ts[2 * l + 1] = '#';
		ts[2 * l + 2] = '$';

		int n = ts.length;
		int[] p = new int[n];
		int center = 0, right = 0;
		for (int i = 1; i < n - 1; i++) {
			int left = 2 * center - i;
			if (right > i) {
				p[i] = Math.min(right - i, p[left]);
			} else {
				p[i] = 0;
			}

			while (ts[i + 1 + p[i]] == ts[i - 1 - p[i]]) {
				p[i] += 1;
			}

			if (i + p[i] > right) {
				center = i;
				right = i + p[i];
			}
		}

		int maxLen = 0;
		int centerIndex = 0;
		for (int i = 1; i < n - 1; i++) {
			if (p[i] > maxLen) {
				maxLen = p[i];
				centerIndex = i;
			}
		}
		int startIdx = (centerIndex - 1 - maxLen) / 2;
		return s.substring(startIdx, startIdx + maxLen);
	}