Manacher算法是O(n)求最长回文子串的算法，其原理很多别的博客都有介绍，代码用的是clj模板里的，写的确实是异常的简洁，现在的我只能理解个大概，下面这个网址的介绍比较接近于这个模板，以后再好好理解，我现在先放一放
http://www.starvae.com/?p=212
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 |
#pragma warning(disable:4996)#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<vector>#include<cmath>using
namespace std;void
palindrome(char
cs[], int
len[], int
n) { //len[i] means the max palindrome length centered i/2 for
(int i = 0; i < n * 2; ++i) { len[i] = 0; } for
(int i = 0, j = 0, k; i < n * 2; i += k, j = max(j - k, 0)) { while
(i - j >= 0 && i + j + 1 < n * 2 && cs[(i - j) / 2] == cs[(i + j + 1) / 2]) j++; len[i] = j; for
(k = 1; i - k >= 0 && j - k >= 0 && len[i - k] != j - k; k++) { len[i + k] = min(len[i - k], j - k); } }}char
str[120000];int
tlen[240000];int
n;int
main(){ while
(~scanf("%s", str)) { palindrome(str, tlen, strlen(str)); int
ans = 0; int
mxlen = strlen(str); for
(int i = 0; i < 2 * mxlen; i++){ ans = max(ans, tlen[i]); } printf("%d\n", ans); } return
0;} |
原文：http://www.cnblogs.com/chanme/p/3561844.html