# O(N) Manacher Algorithm implemented with Java

• ``````    public String longestPalindrome(String s) {
char[] str = preProcess(s).toCharArray();
int N = str.length;
int[] p = new int[N + 1];
int id = 0, mx = 0;
for (int i = 1; i < N - 1; i++) {
p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 0;
while (str[i + 1 + p[i]] == str[i - 1 - p[i]])
p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = 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 pos = (centerIndex - 1 - maxLen) / 2;
return s.substring(pos, pos + maxLen);
}

private String preProcess(String s) {
int len = s.length();
if (len == 0)
return "^\$";
StringBuffer sb = new StringBuffer("^");
for (int i = 0; i < len; i++)
sb.append("#").append(s.charAt(i));
sb.append("#\$");
return sb.toString();
}``````

• Can you explain or provide a link for the algorithm?

• Looks like O(n^2): while in for loop.

• You may just have a search for "Manacher Algorithm", it's a famous O(n) algorithm for Longest Palindromic Substring problem.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.