pat L2-008 复习manacher

马上要去比赛了复习一下最长回文串的长度。

算法的实现两个步骤；

1. 一个是对原串的处理，在所有的空隙位置(包括首尾)插入同样的符号，要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的。

2.用p数组记录以i为中心的回文段的半径实际的长度是p的值-1。然后就是对p数组的求解两种大情况三种小情况这个就不多说了

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

using namespace std;

int main()

{

    int p[1001*2+2];

    string s;

    getline(cin,s);

    string temp;

    temp+="$#";//！！！！ 前面的符号一开始加的是@ wa一万次， 气死老子，

    for(int i=0;i<s.length();i++)// 插入'#'定向处理

    {

        temp+=s[i];

        temp+='#';

    }

    s+='\0';//这个细节也要注意/

    int maxlen=0,id=0;

    memset(p,0,sizeof(p));

    for(int i=2;i<temp.size();i++)

    {

        int k=i-id;

        if(id+p[id]>i) p[i]=min(p[id-k],p[id]-k);// 这里用id+p[id]表示当前最大回文的边界  具体怎么

        else p[i]=1;

        while(temp[i-p[i]]==temp[i+p[i]]) p[i]++;

        if(i+p[i]>id+p[id]) id=i;

        if(maxlen<p[i]) maxlen=p[i];// 这里maxnlen 记录的就是最大的长度

    }

    cout<<maxlen-1<<endl;

    return 0;

}

巴特西

pat L2-008 复习manacher

最新文章

热门文章