首页 > 代码库 > Manacher 最长回文串问题
Manacher 最长回文串问题
有人问你，一个字符串中最长的回文字串是谁？
作为一个 2B 青年， 一年前的我会这样回答：暴力枚举每个字串，判断合法与否？
╮(╯▽╰)╭ 就是没什么戏。。。。
后来，在机房的一个大牛的介绍下，我知道了 Manacher 算法。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。
其实 Manacher 和 KMP 是非常之像的。
令 rad[i] 表示以 第 i 个字符为中心的回文字串的半径长度。
那么我们考虑一下当前最远拓展到 j 编号为 rad[k]，那么我们当前要计算的 rad[i] 有如下几种情况：
i 关于 k 对称的字符为 t = k + k - i. 那么如果 i + rad[t] < j 那么 rad[i] = rad[t]
若 i + rad[t] >= j我们必须 暴力拓展 直到失配为止
这样子的话，复杂度是 O(n) 的。比暴力好了很多。
我们看一下代码：
1 #include<cstdlib> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define maxn 310100 6 using namespace std; 7 char s[maxn],Ma[maxn]; 8 int rad[maxn],Max,L,kase; 9 void manacher(char s[],int L)10 {11 memset(rad,0,sizeof(rad));12 Max = 0;13 int len = 0;14 Ma[len++] = ‘#‘;15 for(int i=0;i<L;++i){16 Ma[len++] = s[i];17 Ma[len++] = ‘#‘;18 }19 int i,j,k;20 for(int i=1,j=0;i<len;i+=k){21 while(Ma[i-j-1] == Ma[i+j+1] && i-j-1>=0 && i+j+1<len)22 j++;23 rad[i] = j;24 Max = max(rad[i],Max);25 for(k=1;k<=rad[i] && rad[i]<rad[i-k]+k;++k)26 rad[i+k] = min(rad[i-k],rad[i]-k),27 Max = max(Max,rad[i+k]);28 j = max(j-k,0);29 }30 }31 int main()32 {33 freopen("manacher.in","r",stdin);34 freopen("manacher.out","w",stdout);35 while(scanf("%s",s)!=EOF){36 if(s[0] == ‘E‘)break;37 L = strlen(s);38 manacher(s,L);39 printf("Case %d: %d\n",++kase,Max);40 }41 return 0;42 }
Manacher 最长回文串问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。