Manacher算法是O(n)求最长回文子串的算法,其原理很多别的博客都有介绍,代码用的是clj模板里的,写的确实是异常的简洁,现在的我只能理解个大概,下面这个网址的介绍比较接近于这个模板,以后再好好理解,我现在先放一放
http://www.starvae.com/?p=212
#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;
}