该算法就是处理一个字符串中的最长回文子串，在后缀数组中看到过相对的解法，时间复杂度可以优化到o(n),但是相对代码量太大，而面对回文串算法有相对更简单的方法，可以很简单的处理出来，代码量小，时间也是o(n)。 Manacher算法是一种dp思想，很好理解，贴出代码，方便以后自己用。
#include <stdio.h> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int Max_N = 110010; int Ma[Max_N * 2]; int Mp[Max_N * 2]; void Manacher(char s[], int len) { int l = 0; Ma[l++] = 1010; Ma[l++] = 1000; for (int i = 0; i < len; i++) { Ma[l++] = int(s[i]); Ma[l++] = 1000; } Ma[l] = 0; int mx = 0, id = 0; for (int i = 0; i < l; i++) { Mp[i] = mx > i? min(Mp[2*id-i], mx-i):1; while (Ma[i+Mp[i]] == Ma[i-Mp[i]]) Mp[i]++; if (i + Mp[i] > mx) { mx = i + Mp[i]; id = i; } } } char buf[Max_N]; int main() { while (scanf("%s", buf) != EOF) { Manacher(buf, strlen(buf)); int len = strlen(buf); int max1 = 0; for (int i = 0; i < 2*len+2; i++) { max1 = max(max1, Mp[i]-1); } cout << max1 << endl; } return 0; }