最长回文子串问题：
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度。回文就是正反读都是一样的字符串,如aba, abba等
求最长回文子串一个很著名的算法就是Manacher算法，时间复杂度为On。通常认为这是最优的算法。但今天我看到一个实测比Manacher跟快的算法，特来分享一下。
Manacher算法：
char str2[maxn], str[maxn]; int len, dp[maxn]; int Manacher() { int ans = 0, maxr = 1, pos = 1; for (int i = 1; i < len; ++i) { dp[i] = maxr > i ? min(dp[pos * 2 - i], maxr - i) : 1; while (str[i - dp[i]] == str[i + dp[i]]) ++dp[i]; --dp[i]; if (maxr < i + dp[i]) { maxr = dp[i] + i; pos = i; } ans = max(ans, dp[i]); } return ans; } int main() { //std::ios::sync_with_stdio(0); //std::cin.tie(0); #ifdef NIGHT_13 freopen("in.txt", "r", stdin); //freopen("myout.txt", "w", stdout); #endif str[0] = '$'; int N = RI(); while (N--) { scanf("%s", str2); len = 0; for (int i = 0; str2[i]; ++i) { str[++len] = '#'; str[++len] = str2[i]; } str[++len] = '#'; str[++len] = 0; printf("%d\n", Manacher()); } return 0; }
更快算法：
char str[maxn]; int Fast() { int ans = 0; for (int i = 1; str[i]; ++i) { int s = i, e = i; while (str[e + 1] == str[s]) ++e; i = e; while (str[s - 1] == str[e + 1]) --s, ++e; ans = max(ans, e - s + 1); } return ans; } int main() { //std::ios::sync_with_stdio(0); //std::cin.tie(0); #ifdef NIGHT_13 freopen("in.txt", "r", stdin); //freopen("myout.txt", "w", stdout); #endif str[0] = '$'; int N = RI(); while (N--) { scanf("%s", str + 1); printf("%d\n", Fast()); } return 0; } 实测对比：HDU:
POJ：
