# My implement of Manacher's algorithm using C

• p array is used to record the palindrome length if we use each point as the central point in the new string.

``````/* Reference:
* https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher.27s_algorithm
* http://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Part-II.html
*/

char* longestPalindrome(char* s) {
int len = strlen(s);

int length = (len << 1) + 1;
char *str = (char *)malloc(sizeof(char) * length);
int *p = (int *)malloc(sizeof(int) * length);
for (int i = 0; i < length; ++i) {
str[i] = i % 2 ? s[i / 2] : '\0';
//p[i] = 0; // assigned when distance < 0
}

int mid = 0, right = 0;
for (int i = 0; i < length; ++i) {
int distance = right - i;
int i_mirror = mid - (i - mid);

if (distance > 0 && p[i_mirror] < distance) // when i is in the right mirror of a big palindrome, use the value of left mirror
p[i] = p[i_mirror];
else {
p[i] = distance < 0 ? 0 : distance;
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < length
&& str[i - p[i] - 1] == str[i + p[i] + 1])
++p[i];
mid = i;
right = i + p[i];
}
}

int pos = 0, maxlen = 0;
for (int i = 0; i < length; ++i) {
if (p[i] > maxlen) {
pos = i;
maxlen = p[i];
}
}

free(str);
free(p);

char *res = s + (pos - maxlen) / 2;
*(res + maxlen) = '\0';
return res;
}``````

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