# C solution using Manacher's algorithm (3ms)

• ``````#define MIN(x, y)		((x) < (y)) ? (x) : (y)
#define MAX_LEN			1000
#define MANACHER_LEN(len)	((len) * 2 + 3)
#define MAX_MANACHER_LEN	MANACHER_LEN(MAX_LEN)
#define MANACHER_START_CHAR	'^'
#define MANACHER_SPECIAL_CHAR	'#'
#define MANACHER_END_CHAR	'\$'

char* longestPalindrome(char* s) {
int slen = strlen(s);
if (slen <= 1)
return s;

/*
*  Convert T string from S string,
*  for example, S = "abaaba", T = "^#a#b#a#a#b#a#\$"
*/
char T[MAX_MANACHER_LEN];
int tlen = MANACHER_LEN(slen);
T[0] = MANACHER_START_CHAR;
T[1] = MANACHER_SPECIAL_CHAR;
for (int i = 0, j = 2; i < slen; i++, j+=2) {
T[j] = s[i];
T[j + 1] = MANACHER_SPECIAL_CHAR;
}
T[tlen - 1] = MANACHER_END_CHAR;

/*
*  Manacher's algorithm
*  Reference: https://articles.leetcode.com/longest-palindromic-substring-part-ii
*/
unsigned short P[MAX_MANACHER_LEN];
int C = 0, R = 0;
int center_idx = 0, max_len = 0;
for (int i = 2; i < tlen - 2; i++) {
int i_mirror = C * 2 - i; // i' = C - (i - C)
P[i] = (R > i) ? MIN(R - i, P[i_mirror]) : 0;
while (T[i - P[i] - 1] == T[i + P[i] + 1])
P[i]++;

if (i + P[i] > R) {
C = i;
R = i + P[i];
}

if (P[i] > max_len) {
center_idx = i;
max_len = P[i];
}
}

int lps_idx = (center_idx - max_len - 1) / 2;
s[lps_idx + max_len] = '\0';
return &s[lps_idx];
}
``````

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