```
/**
*
* Technically, Manacher O(n) should beat traditional method O(n^2)
*
* But, because of the limitation of test cases, they perform identically the same.
* Also, O(c1*n) O(c2 * n^2) c1 is larger than c2 apparently out of Manacher's doing more checks in one move.
*
* It is hard to explain Manacher with several lines.
* I strongly recommend a video for you. Please watch it at least three time before telling yourself you cannot understand it.
*
* here is the link: [https://www.youtube.com/watch?v=V-sEwsca1ak&t=332s](https://www.youtube.com/watch?v=V-sEwsca1ak&t=332s)
*
*/
public class Solution {
public String longestPalindromeTradition(String s) {
char[] arr = s.toCharArray();
int l = 0;
int r = 0;
int left = 0;
int right = 0;
int len = arr.length;
int upper = len;
while (right < upper) {
while (right + 1 < len && arr[right + 1] == arr[right]) {
right ++;
}
int copy = right;
while (left - 1 >= 0 && right + 1 < len && arr[left - 1] == arr[right + 1]) {
left --;
right ++;
}
if (right - left > r - l) {
r = right;
l = left;
upper = len - ((right - left) >> 1);
}
left = ++copy;
right = left;
}
return s.substring(l, r + 1);
}
public String longestPalindromeManacher(String s) {
int l = 0;
int r = 0;
int len = (s.length() << 1) + 1 ;
char[] arr = new char[len];
arr[0] = '^';
char[] temp = s.toCharArray();
int j = 0;
for (int i = 1; i < arr.length; ++ i) {
arr[i] = temp[j ++];
arr[++ i] = '^';
}
int[] count = new int[arr.length];
int maxLen = 0;
int currLen = 0;
int center = 0;
int upper = len;
while (center < upper) {
// expand
int half = currLen >> 1;
int left = center - half;
int right = center + half;
while (left - 1 >= 0 && right + 1 < len && arr[left - 1] == arr[right + 1]) {
left --;
right ++;
}
count[center] = right - left + 1;
// update result
if (count[center] >= maxLen) {
l = left;
r = right;
upper = len - (maxLen >> 1);
maxLen = count[center];
}
// findNextCenter
int nextCenter = -1;
for (int i = 1 + center; i <= right; i ++) {
int mirror = count[(center << 1) - i];
int exRight = (mirror >> 1) + i;
if (exRight == right) {
nextCenter = i;
currLen = mirror;
break;
} else if (exRight < right) {
count[i] = mirror;
} else {
count[i] = 1 + ((right - i) << 1);
}
}
if (nextCenter == -1) {
center = right + 1;
currLen = 0;
} else {
center = nextCenter;
}
}
return getResult(arr, l, r);
}
public String getResult(char[] arr, int left, int right) {
char[] res = new char[(right - left) >> 1];
int j = 0;
for (int i = left + 1; i < right; i ++) {
res[j++] = arr[i++];
}
return new String(res);
}
}
```