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;
    }
}