1.概念:回文序列,是指一个字符串中存在一组连续的子串,从前往后和从后往前式一样的。
形容526412332189中的123321就是回文序列
2.如何求解字符串中的回文序列呢?这里介绍三种方法。
1)暴力求解法
对于字符串开始遍历,定义两个指标i和j分别从i=0,j=n-1开始循环逐一比对,i++,j--
图片说明

2)中心扩散法
基本思想,循环字符串中的每一个字符,以该字符为中心向两边进行扩散,这里采用循环扩散,逐一比对,相等则加一,否则跳出循环,然后保存半径长度及中心的位置。
缺点:回文序列为奇数和偶数时必须分开讨论,稍微复杂。
3)manacher算法,又称马拉车算法
1.针对上面中心扩散法的缺点,该算法首先提出了一个完美的解决方案,即对于一个n的字符串,有n-1个空隙则插入#(符号必须不能与字符串中元素重复),再在字符串的首尾加#符号,此外为保证字符串不发生溢出的现象,再在字符串的首位添加一个其他符号例如*
例如:*#5#2#6#4#1#2#3#3#2#1#8#9#
再采取上述中心扩散法的程序代码:

string append(string s){
    string reg="*#";
    for(int i=0;i<s.size();i++){
        reg+=s[i];
        reg+="#";
    }
    return reg;
}
int main(){
    string s1;
    while(cin>>s1){
        string s=append(s1);//进行预处理,插字符
        int n=s.size();
        vector<int>v(n);
        v[0]=0;
        v[n-1]=0;
        for(int i=1;i<s.size()-1;i++){
            int num=0;
            for(int j=0;j<i;j++){
                if(s[i-j]==s[i+j])
                    num++;
                else
                    break;
            }
            v[i]=num;#这里只保存半径长度,也可以定义一个vector<pair>类型保存位置
        }
        sort(v.begin(),v.end(),greater<int>());//输出回文序列最长的字符串
        cout<<v[0]-1<<endl;
    }
}

2.为了简化上面代码,引入了马拉车算法
该算法的基本思想就是:对于上面每一个字符都有一个半径长度,为一个数组p[],假设已经知道了该数组的前i-1项的数目,能不能简化下求p[i]的值。
我们把一个数组看成一个数轴,则前面i-1项中,每一项都有三个特征值,即中心位置,半径长度,以及能达到最右边的值,我们可以取出其中的最大值max=i+p[i];即是能达到最右边的值
图片说明
这里我们要对i进行讨论
第一,如果i的位置位于max的左边,那我们必然可以通过对称性在中心的右边找到一个j对称点,
此时又分两种情况,p[j]的值多大?
如果j的左边半径的长度大于mx的对称点,即j的回文长度是位于cn的范围下的,这里就可以通过回文序列对称的思想直接进行赋值p[i]=p[j]
如果,j的左边长度超出了cn的范围,如上图的蓝色方框所示,这里我们可以看出i的半径长度应该是max-i的长度再加上超出的部分
所以综上所述,我们应该取min(p[j],max-i)长度中的小的那一个进行赋值,再计算超出部分。
第二,如果i位于max的右边,我们则无法从前面的i-1项得出有用的信息,由于半径长度计算从自身开始,我们先赋值p[i]=1;然后开始运用中心扩散的思想进行对比。
具体代码如下:

string append(string s){
    string reg="*#";//
    for(int i=0;i<s.size();i++){
        reg+=s[i];
        reg+="#";
    }
    return reg;
}
int main(){
    string s1;
    while(cin>>s1){
        string s=append(s1);
        int n=s.size();
        vector<int>v(n);
        v[0]=0;
        int id=0;
        int max=0;
        for(int i=1;i<n;i++){
            if(max>i)
                v[i]=min(max-i,v[2*id-i]);
            else
                v[i]=1;
            while(s[i+v[i]]==s[i-v[i]]){//这里开始循环逐一对比
                v[i]++;
            }
            if(max<i+v[i]){
                max=i+v[i];
                id=i;
            }
        }
        sort(v.begin(),v.end(),greater<int>());
        cout<<v[0]-1<<endl;
    }
}