问题说明：
如果给出字符串S=A1A2.An，则必须找到最长回文子串(Longest Palindromic Substring )。 回文部分列是指有s的部分列Ai.mrdyb为回文。 例如，对于字符串S=abcdcbeba，其回文子串是bcdcb、cdc、beb，而满足标题要求的最长回文子串是bcdcb。
推理的想法：
1 .回文可能由奇数字符组成，也可能由偶数字符组成。 奇数回文的处理很直观，以某个字符为中心向两侧依次扩展即可。 因此，可以将对偶数次语句的处理转换为对奇数次语句的处理。 在文字边界添加特殊符号。 例如，对于字符串aba，在预处理后#a#b#a#； 对于字符串abba，预处理后为#a#b#b#a。 可以看出，无论是奇数回文还是偶数回文，在与处理后都会变成奇数回文。 找到与预处理字符串的最长回文后，删除所有#即成为源字符串的最长回文。
2 .对于寻找字符串某一类子串的问题，最简单直观的想法是列举所有子串逐一进行判别。 这里也不例外，当然时间的复杂性也很高，是o(n^3)。
3 .对于这个问题，我们可以进行一定程度的简化处理。 回文是特殊字符串，所以可以以源字符串的各字符为中心，依次查找最长回文子串P0，P1，Pn。 可以求出这些最长回文部分列中的最长列pi=max(p1，P2，Pn )。 请参阅源代码：
string find _ LPS _ native (conststringstr )
{
intcenter=0，max_len=0；
for(inti=1； I
{
intj=1；
以str[i]为中心，向两侧依次扩展，寻找最长回文Pi
while(Ij=0STr(Ij )==str(I-j ) ) ) ) ) )。
j；
-j；
if(j1jmax_len ) ) ) ) ) ) ) ) ) )。
{
center=i；
max_len=j；
}
}
return str.substr (center-max_len，) max _ len
}
4 .可见上述做法的复杂度为o(n^2)。 与囊括字符串的做法相比，已经降低了一位的复杂性。 但是仔细想想。 上面的算法有改进的余地吗？ 当然有！ 而且通过改善，可以将复杂度降低到O(N )！ 这就是有名的mana cher’salgorithm。 请参阅以下分析：
例如：对于字符串S=abcdcba来说，最长回文部分列是以d为中心的半径为3的部分列。 用上述方法分别求出以S[1]=a，S[2]=b，S[3]=c，S[4]=d为中心的最长回文子串后，需要将S[5]=c，S[6]=b . 答案是否定的。 因为找到了以d为中心的半径为3的回文，所以以S[5]和S[3]，S[6]和S[2] .S[4]为对称中心。 因此，在以S[5]、S[6]为中心扩展并取回字符串时，利用已经发现的关于S[3]、S[2]的信息，直接以一定的步骤错开，从而能够减少比较的次数(KMP中的nep ) 找到了优化的想法。 让我们先看看代码：
string find _ LPS _ advance (conststringstr )
{
//findradiusofallcharacters
Vectorp(str.Length )，0 )；
intidx=1，max=0；
for(inti=1； I
{
是if(maxi )
{
p[i]=p[(idx )
}
(wile(str[Ip[I]1)==str[I-p[I]-1] ) ) ) ) ) ) 65
p[i]=1；
if(Ip[I]max ) )。
{
idx=i；
max=i p[i]；
}
}
//findthecharacterwhichhasmaxradius
intcenter=0，radius=0；
for(inti=0； I
{
if(p[I]radius ) )。
{
center=i；
radius=p[i]；
}
}
returnstr.substr(center-radius，) radius
}
在这里简单说明一下。 上述代码有三个主要变量，它们的含义如下：
p:以S[i]为中心的最长回字符串的半径为p[i]。
idx:找到了回文子串的起始位置，可以向右延伸最远的距离。
max:已经找到的可以向右延伸最远距离的回文子串末尾的位置。
算法的主要思想是先找到所有的p[i]，最大的p[i]求得。 p[i] (求Ji时，使用已经求出的p[i]减少比较次数。
代码中重要的是：
p[i]=p[(idx )
在求p[i]时，如果是maxi，则表示已经求出的最长回文中包含p[i]，关于p[i]和idx对称的p[[idx1]-I]的最长回文子串可以提供一定的信息。 如果你看两幅图，你可能会明白它的意思：
求出两者的最小值是因为现在可以得到的信息来自max的左侧，进而进行比较，有必要求出以S[i]为中心的最长回字符串。
5 .除了上述几种方法之外，还可以使用动态规划和后缀树来求解。 下次介绍。
在结束文章之前，关于字符串类问题，我建议多画画，寻找其规律。