Manacher算法笔记中，如何处理长尾词的匹配问题？
- 内容介绍
- 文章标签
- 相关推荐
本文共计766个文字，预计阅读时间需要4分钟。
Part 1: 算法概述该算法由Glenn K. Manacher于1975年提出，是一种在O(N)时间复杂度下求解字符串所有回文子串的算法，也是寻找最大回文子串最高效的方法。算法的难点主要在于理解。
part 1 算法简述该算法由 Glenn K. Manacher 在 1975 年提出，是一种可以在O(N)时间复杂度下求字符串所有回文子串的算法，也是求最大回文子串最高效的算法。该算法的难度主要在于理解。
求最大回文字串，首先要注意奇回文串与偶回文串的区别，如果不进行处理统一，就会使代码变得很复杂。
那么怎么来统一呢？
可以在每两个字符之间加上字符串中不曾出现的字符（包括头和尾），这样就可以使得字符串长度变为奇数，原因如下：
\(设原字符串长度为k,则经过操作后变为2k+1,必定为奇数.\)
例如：
解决了字符串统一的问题，接下来需要思考怎么优化求最大回文字串的过程。（\(O(n^2)\)的暴力算法在此不做介绍）
按照以往的经验，减少求回文的次数是关键，我们需要尽量使用已经拥有的数据。
此处分成两种情况：
-
1. 当前枚举的回文中心点在最大回文串内。
这种情况，是最简单的情况，我们可以运用回文的对称性，使用大回文串的另一边的对称点的数据。当然，万一可以更大呢？所以还是要在该数据的基础上继续尝试扩张。
-
2. 当前枚举的回文中心不在最大回文串内。
那就调用朴素算法进行计算。
模板题：HDU 3068 最长回文
#include<bits/stdc++.h>
using namespace std;
char a[1100010];
char b[1100010];
long long ln;
void chuli(){//对字符串进行处理
ln=0;
b[ln++]='@';
long long lenn=strlen(a);
for(long long i=0;i<lenn;i++){
b[ln++]='#';
b[ln++]=a[i];
}
b[ln++]='#';
}
long long len[1100010],ans;
void huiwen(){
memset(len,0,sizeof(len));
long long p=0,po=0;
ans=0;
for(long long i=1;i<ln;i++){
if(i<p){//分类讨论
len[i]=min(len[2*po-i],p-i);
}else{
len[i]=1;
}
while(b[len[i]+i]==b[i-len[i]]){//尝试扩张
len[i]++;
}
if(len[i]+i>p){//更新最大回文串
p=len[i]+i;
po=i;
}
ans=max(ans,len[i]);//更新答案
}
}
int main(){
while(~scanf("%s",a)){
chuli();
huiwen();
printf("%lld\n",ans-1);
}
}
part 4 参考文章
1.rwbyblake：manacher介绍及图文讲解（用于求解最长回文子串）
2.oi-wiki：Manacher
本文共计766个文字，预计阅读时间需要4分钟。
Part 1: 算法概述该算法由Glenn K. Manacher于1975年提出，是一种在O(N)时间复杂度下求解字符串所有回文子串的算法，也是寻找最大回文子串最高效的方法。算法的难点主要在于理解。
part 1 算法简述该算法由 Glenn K. Manacher 在 1975 年提出，是一种可以在O(N)时间复杂度下求字符串所有回文子串的算法，也是求最大回文子串最高效的算法。该算法的难度主要在于理解。
求最大回文字串，首先要注意奇回文串与偶回文串的区别，如果不进行处理统一，就会使代码变得很复杂。
那么怎么来统一呢？
可以在每两个字符之间加上字符串中不曾出现的字符（包括头和尾），这样就可以使得字符串长度变为奇数，原因如下：
\(设原字符串长度为k,则经过操作后变为2k+1,必定为奇数.\)
例如：
解决了字符串统一的问题，接下来需要思考怎么优化求最大回文字串的过程。（\(O(n^2)\)的暴力算法在此不做介绍）
按照以往的经验，减少求回文的次数是关键，我们需要尽量使用已经拥有的数据。
此处分成两种情况：
-
1. 当前枚举的回文中心点在最大回文串内。
这种情况，是最简单的情况，我们可以运用回文的对称性，使用大回文串的另一边的对称点的数据。当然，万一可以更大呢？所以还是要在该数据的基础上继续尝试扩张。
-
2. 当前枚举的回文中心不在最大回文串内。
那就调用朴素算法进行计算。
模板题：HDU 3068 最长回文
#include<bits/stdc++.h>
using namespace std;
char a[1100010];
char b[1100010];
long long ln;
void chuli(){//对字符串进行处理
ln=0;
b[ln++]='@';
long long lenn=strlen(a);
for(long long i=0;i<lenn;i++){
b[ln++]='#';
b[ln++]=a[i];
}
b[ln++]='#';
}
long long len[1100010],ans;
void huiwen(){
memset(len,0,sizeof(len));
long long p=0,po=0;
ans=0;
for(long long i=1;i<ln;i++){
if(i<p){//分类讨论
len[i]=min(len[2*po-i],p-i);
}else{
len[i]=1;
}
while(b[len[i]+i]==b[i-len[i]]){//尝试扩张
len[i]++;
}
if(len[i]+i>p){//更新最大回文串
p=len[i]+i;
po=i;
}
ans=max(ans,len[i]);//更新答案
}
}
int main(){
while(~scanf("%s",a)){
chuli();
huiwen();
printf("%lld\n",ans-1);
}
}
part 4 参考文章
1.rwbyblake：manacher介绍及图文讲解（用于求解最长回文子串）
2.oi-wiki：Manacher