hdu 3068 最长回文（O(n)求回文串，manacher算法模板题）
题目链接 题意：求一个字符串中的最长回文串。 思路：昨天武大校赛遇到了一个manacher算法的题。。。我竟然听都没听过。。。
于是去学习了一发。
感觉这篇博客讲得最详细manachar算法学习
于是切了个模板题练手。
先简单说下我对这个算法的理解，等做一些题目以后再来总结一发。 我觉得manachar算法最关键的一点是，如果你枚举回文串的中心位置，当你枚举到i的时候，那么i之前的位置回文串长度的最大值是已经确定的了。 换句话说，后面的中心位置不会影响前面的中心位置的答案。 于是可以利用前面已经做过的匹配来获得一些信息，避免了重复。 不过讲真。。。O(n)的复杂度。。这算法还是相当让人感到震撼的。。。 更具体的部分见代码注释。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年04月18日 星期一 14时06分59秒
4File Name :code/hdu/3068.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E6+999;
7char st[N];
8int p[2*N]; //p[i]为以第i个位置的字符为中心的回文串的半径长，默认为1.
1int manachar( char *s)
2{
3 int len = strlen(s);
4 int id = 0; //id表示之前位置的能延伸到最远位置的字符串的中心位置。
5 int maxlen = 0 ; //maxlen是为了更新答案而用。。。就是记录了一个最大值。。。
6 int mx = 0 ;//mx为当前位置之前的回文串能延伸到的最远位置 即：max(p[j]+j) (j<i)
7 //如果知道之前能延伸到最远位置的字符串的中心位置的下标为id，那么就是p[id]+id;
8 for ( int i = len ; i >= 0 ; i--) //插入'#'是为了将字符串长度奇偶性不同的统一考虑。
9 {
10 s[i+i+2] = s[i];
11 s[i+i+1] = '#';
12 }
13 s[0]='*'; //s[0] ='*'以及用字符数组最后默认的s[len+len+2]='\0'是为了下面while 循环的时候不溢出。。
14 //两边的字符一定要不一样。。用string的话记得两边都加字符。。。
15 for ( int i = 2 ; i < 2*len+1 ; i++)
16 {
17 if (p[id]+id>i) p[i] = min(p[2*id-i],p[id]+id-i);
18 else p[i] = 1;
19 while (s[i-p[i]]==s[i+p[i]]) p[i]++;
20 if (id+p[id]<i+p[i]) id = i;
21 if (maxlen<p[i]) maxlen = p[i];
22 }
23 return maxlen-1;
24 //这道题是问最长回文串的长度。。。如果是问回文串是什么的话。。。根据id和maxlen也可以构造出来。。。
25}
26int main()
27{
28 #ifndef ONLINE_JUDGE
29 freopen("code/in.txt","r",stdin);
30 #endif
1 while (~scanf("%s",st))
2 {
3 int ans = manachar(st);
4 printf("%d\n",ans);
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}