好不容易看懂这个算法，赶紧记下来。。。 回文串就是一个不论是从前往后看还是从后往前看都是一样的一个字符串。在求回文串的时候难免会有因为串的长度为奇数还是偶数来分情况讨论，manacher算法为了避免这个问题，在字符串的前端和尾部以及中间位置都插入一个与该字符串无关的一个字符。例如字符串ababab，经过处理就会得到#a#b#a#b#a#b#,这样不管这个字符串在开始时为奇数还是偶数，经过处理都会变成一个奇数个字符的字符串。 然后引入一个辅助数组p[]，p[i] 记录的是以i为中心回文串的半径。 例如：
s[] = “# a # b # a # b # a # b #” p[] =”1 1 1 3 1 1 1 5 1 1 1 1 1”
这个算法的重点就在于怎么计算出这个p[]数组，因为我们是从左至右扫描这个字符串，所以当我们以i为回文串的中心时，我们一定是已经知道以i之前所有点为中心的回文串长度。我们借助两个辅助变量 id 和 mx，id为已知的 {右边界最大} 的回文子串的中心，mx则为id+P[id]，也就是这个子串的右边界。
如下图所示，id是已知的右边界最大的回文串的中心，mx为其右边界，i为我们当前拟定为的一个回文串中心，j是i关于id的对称点，因为id是已知的回文串，那么在红色的那条线的范围内的字符串关于id对称，那么当p[j] < mx - i时，p[i] = p[j];
但是当p[j] > mx - i 时，p[i] = mx - i;因为mx的对称点前面的字符虽然对于j来说是对称的，但是因为mx后面的字符与mx对称点前边的字符已经不对称了，所以i的回文串半径对于j来说只能匹配到mx处。这个地方就利用了回文串的对称性让我们减少了重复计算。在得到p[i]的初步结果后，再从我们刚刚得到的i的半径处往下比较，如果后边还有相同的就把半径增加。
具体代码如下：
int min(int a, int b) { return a > b ? b : a; } int* manacher(char* s) { int len = strlen(s); int id = 0, i = 0, mx = 0; int *p = (int *)malloc((len * 2 + 1) * sizeof(int)); for(i = 0; i < len * 2 + 1; i++) *(p + i) = 0; for(i = 0; s[i] != '\0'; i++) { p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1; while(s[i + p[i]] == s[i - p[i]]) p[i]++; if(mx < i + p[i]) { mx = i + p[i]; id = i; } } return p; } char* longestPalindrome(char* s) { int len = strlen(s), i, j = 0,max = 0, index; if(len == 1) return s; char *ans = (char *)malloc((len + 1) * sizeof(char)); char *str = (char *)malloc((len * 2 + 1) * sizeof(char)); int *cnt = (int *)malloc((len * 2 + 1) * sizeof(int)); for(i = 0; s[i] != '\0'; i++) { *(str + j) = '#'; j++; *(str + j) = *(s + i); j++; } *(str + j) = '\0'; cnt = manacher(str); for(i = 0; i < len * 2 + 1; i++) { if(*(cnt + i) >= max) { max = *(cnt + i); index = i; } } int k = 0; j = index - max; for(i = j + 1; i < j + max * 2; i ++) { if(*(str + i) != '#') { *(ans + k) = *(str + i); k++; } } *(ans + k) = '\0'; return ans; }