Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题目链接 题意：求一个字符串中的最长回文串。 思路：昨天武大校赛遇到了一个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
26
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32const int N=2E6+999;
33char st[N];
34int p[2*N]; //p[i]为以第i个位置的字符为中心的回文串的半径长，默认为1.
35
36
37int manachar( char *s)
38{
39 int len = strlen(s);
40 int id = 0; //id表示之前位置的能延伸到最远位置的字符串的中心位置。
41 int maxlen = 0 ; //maxlen是为了更新答案而用。。。就是记录了一个最大值。。。
42 int mx = 0 ;//mx为当前位置之前的回文串能延伸到的最远位置 即：max(p[j]+j) (j<i)
43 //如果知道之前能延伸到最远位置的字符串的中心位置的下标为id，那么就是p[id]+id;
44 for ( int i = len ; i >= 0 ; i--) //插入'#'是为了将字符串长度奇偶性不同的统一考虑。
45 {
46 s[i+i+2] = s[i];
47 s[i+i+1] = '#';
48 }
49 s[0]='*'; //s[0] ='*'以及用字符数组最后默认的s[len+len+2]='\0'是为了下面while 循环的时候不溢出。。
50 //两边的字符一定要不一样。。用string的话记得两边都加字符。。。
51 for ( int i = 2 ; i < 2*len+1 ; i++)
52 {
53 if (p[id]+id>i) p[i] = min(p[2*id-i],p[id]+id-i);
54 else p[i] = 1;
55 while (s[i-p[i]]==s[i+p[i]]) p[i]++;
56 if (id+p[id]<i+p[i]) id = i;
57 if (maxlen<p[i]) maxlen = p[i];
58 }
59 return maxlen-1;
60 //这道题是问最长回文串的长度。。。如果是问回文串是什么的话。。。根据id和maxlen也可以构造出来。。。
61}
62int main()
63{
64 #ifndef ONLINE_JUDGE
65 freopen("code/in.txt","r",stdin);
66 #endif
67
68 while (~scanf("%s",st))
69 {
70 int ans = manachar(st);
71 printf("%d\n",ans);
72
73 }
74
75 #ifndef ONLINE_JUDGE
76 fclose(stdin);
77 #endif
78 return 0;
79}