个人理解

算法思想

关于马拉车算法，网上的算法教程很多，很明确的指出马拉车算法的精华：
P[i]= mx > i+p[i] ? min（ p[2*id-i] , mx-i ）：1；
p[i]维护回文串的长度，mx是预处理后的字符串中回文串能到达的最右端，id是到达最右端时的中点。

为了方便介绍，这里令 j=2*id-i;
如图，很明显，当mx大于当前遍历字符串i点+其回文长度时，此时可以发现 i 点和 j 点关于id对称，
因为id的回文右端到达mx点，这时p[j] 是已经被计算的 。
假如 mx-i>=p[j] 即 i到以id为中点的回文串最右端mx比以j 为中心的回文串长度大，那么此时p[i]的值至少是P[J]；
当 mx-i< p[j] 时，此时以j 为中心的回文串长度比i到 i到以id为中点的回文串最右端mx 大，那么关于中心点id 对称的 p[j] 部分值无法得到匹配（大于mx部分），此时p[i]的值至少是mx-i 。


下面是最近学习马拉车算法做题的经历，B题用两发dp过不去，才跑去学Manacher，不过vj不能用万能头和不能直接用min也直接编译错误了几发，实际上很久之前参加算法组考核就接触了马拉车算法，不过那时候还是个只会暴力和贴模板的少年（虽然现在也是），不当回事，没有真正去学习。不过感觉马拉车算法并没有那么常见，最大的收获应该就是马拉车算法的思想。个人觉得算法学习一定不能仅仅记住算法的代码实现，只有真正理解一个算法的精髓，就算忘记了代码的实现，也可以自己推出来，这应该才是学习的不二法门。


本人可以说是新手中的新手，欢迎交流。

模板

string Manacher(string s1){
    string s="$#"; //开头存放两个与题目无相关的字符进行初始化
    for(int i=0;i<s1.size();i++)
        s+=s1[i],s+="#";
    vector<int>p(s.size(),0); // p数组进行存储回文串的长度
    int id=0,mx=0,maxpoint=0,maxlen=0; //mx是回文串到达的最右端 id是mx对应的回文串中点 maxpoint是最长回文串的中点 maxlen是最长回文串的长度
    for(int i=1;i<s.size();i++){
        p[i]=mx>i+p[i]?min(mx-i,p[2*id-i]):1;  //这一句是关键点 详解见
        while(s[i+p[i]]==s[i-p[i]]) ++p[i];  // 匹配串的过程
        if(i+p[i]>mx) id=i,mx=i+p[i]; //更新右端和中心点
        if(p[i]>maxlen) maxlen=p[i],maxpoint=i; //更新最大长度和对应中点
    }
    return s1.substr( (maxpoint-maxlen)/2 , maxlen-1 ); //这里范围的是s1中的最长回文串
    // 根据题目需要可 return maxlen / maxpoint 
}

* 例题

A - Palindrome

原题链接：传送门

思路：

1. 很经典的模板题，给定字符串求最长回文子串长度。
   
   代码如下：

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
string Manacher(string s1)
{
    string s="$#";
    for(int i=0;i<s1.size();i++)
        s+=s1[i],s+="#";
    vector<int>p(s.size(),0);
    int id=0,mx=0,maxlen=0,maxpoint=0;
    for(int i=0;i<s.size();i++)
    {
        p[i]=mx>i?min(p[2*id-i],mx-i):1;
        while(s[i+p[i]]==s[i-p[i]]) ++p[i];
        if(mx<i+p[i]) id=i, mx=i+p[i];
        if(maxlen<p[i]) maxlen=p[i],maxpoint=i;
    }
    return s.substr( (maxpoint-maxlen)/2, maxlen-1);
}
int main()
{
    string s;
    int ans=1;
    while(cin>>s)
    {
        if(s=="END") break;
        s=Manacher(s);
        cout<<"Case "<<ans++<<": "<<s.size()<<endl;
    }
    return 0;
}

B - 吉哥系列故事——完美队形II

原题链接：传送门

思路：

1. 题意求的同样是回文，不过多了要求这个回文子串从中点向两边非严格递减，同样的预处理的时候需要用不会影响题目的数字（负数和0等等）来组成新的队列。
2. 扩展回文子串时需要多一句 s[i-p[i]]<=s[i-p[i]+2] 来进行限制从中点向两边非严格递减，至于为什么+2？因为相邻的数是预处理时添加的负数或0，不会影响原串的回文判定。
   
   代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int manx=1e5+5;
int a[manx],b[manx*2];
int n;
int Manacher()
{
    b[0]=-1,b[1]=0;
    int x=2;
    for(int i=1;i<=n;i++) b[x++]=a[i],b[x++]=0;
    vector<int>p(2*n+1,0);
    int mx=0,id=0,maxlen=0;
    for(int i=1;i<x;i++)
    {
        p[i]=mx>i?min(mx-i,p[2*id-i]):1;
        while(b[i-p[i]]==b[i+p[i]]&&b[i-p[i]]<=b[i-p[i]+2]) ++p[i];
        if(mx<p[i]+i) id=i,mx=p[i]+i;
        if(maxlen<p[i]) maxlen=p[i];
    }
    return maxlen-1;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        cout<<Manacher()<<endl;
    }
    return 0;
}

C - Girls’ research

原题链接：传送门

思路：

1. 同样是求回文串，不过这道题目多了串的修改。
2. 给定字符 c 是 ‘a’ , 利用这一条件对字符串进行解密，随后进行正常的马拉车算法操作。
   
   代码如下：

#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
void Manacher(string s1)
{
    string s="$#";
    for(int i=0;i<s1.size();i++)
        s+=s1[i],s+="#";
    vector<int>p(s.size(),0);
    int mx=0,id=0,maxpoint=0,maxlen=0;
    for(int i=1;i<s.size();i++)
    {
        p[i]=mx>p[i]+i?min(p[2*id-i],mx-i):1;
        while(s[i+p[i]]==s[i-p[i]]) ++p[i];
        if(mx<p[i]+i) id=i,mx=p[i]+i;
        if(maxlen<p[i]) maxlen=p[i],maxpoint=i;
    }
    if(maxlen>3){
        cout<<(maxpoint-maxlen)/2<<" "<<(maxpoint-maxlen)/2+maxlen-2<<endl;
        cout<<s1.substr( (maxpoint-maxlen)/2, maxlen-1)<<endl;
    }
    else puts("No solution!");
}
int main()
{
    string s;
    char c;
    int ans;
    while(cin>>c>>s){
        ans=c-'a';
        for(int i=0;i<s.size();i++)
        {
            if(s[i]>=c) s[i]=s[i]-ans;
            else s[i]=s[i]+26-ans;
        }
        Manacher(s);
    }
    return 0;
}

D - Making Huge Palindromes

原题链接：传送门

思路：

1. 求给右端添加最少字符使出现回文串，求回文串的长度最小值。
2. 算是马拉车的变形，可直接求当mx到达预处理串的最右端时的回文串长度ans， 那么原串长度的两倍减去ans 便是所求的答案。
   
   代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int Manacher(string s1)
{
    string s="$#";
    for(int i=0;i<s1.size();i++)
        s+=s1[i],s+="#";
    vector<int>p(s.size(),0);
    int mx=0,id=0,ans=0;
    for(int i=1;i<s.size();i++)
    {
        p[i]=mx>i+p[i]?min(p[2*id-i],mx-i):1;
        while(s[p[i]+i]== s[i-p[i]]) ++p[i];
        if(p[i]+i>mx) mx=i+p[i],id=i,ans=p[i];
    }
    return ans-1;
}
int main()
{
    int t,T=1;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int ans=Manacher(s);
        cout<<"Case "<<T++<<": "<<2*s.size()-ans<<endl;
    }
    return 0;
}

最后

以上就是靓丽小霸王为你收集整理的关于Manacher/马拉车算法的个人总结个人理解* 例题的全部内容，希望文章能够帮你解决关于Manacher/马拉车算法的个人总结个人理解* 例题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。