问题的说明
回文串是指左右对称的字符串，如aba、abba、cccbccc、aaaa。
输入字符串Str，输出Str内最长回文子串的长度。
完美保温杯：暴力解决
调查各个部分列，判断该部分列是否为回文列，最后判断该部分列是否为最长的回文部分列。
遍历子串的复杂度为O(n^2，判断是否为回文串的复杂度为o[n]，因此该算法的复杂度为O(n^3)。
方法2 :动态规划法
用二维数组ai表示从第I到第j的部分列是否是回文串，在判断从第I到第j的部分列是否是回文串时，可以看从i 1到j-1是否是回文串，然后判断I位和j位是否相同在该算法中，遍历子串的复杂度仍然为o[n^2]，但为了判断回文串的复杂度是否降至o[1]，该算法的复杂度为o[n^2]。 但该算法占用了o(n ) 2的空间。
方法3 :中心扩张法
wldzs在任何一个回文列中都有对称轴，从这个中心的位置向两侧扩展，可以得到以此为中心的最长回文列。 但是请注意，该对称轴的位置可能是一个字符，也可能是两个字符之间的中间。 遍历对称轴位置，复杂度为o[n]，如果找到以该对称轴为中心的最长回文串，复杂度为o[n]，因此该算法的复杂度为O(n^2)。 该算法优于动态规划的是其空间复杂度仅为o(1)。
#包含
#包含
用户命名空间STD；
#define LEN 1000
int main () )。
char str[LEN]；
cinstr；
intlen=strlen(str；
int maxlen=0，mx；
for(intI=0； I
mx=1；
for(intj=1； (i-j=0) ) i j
if(str[I-j]==str[Ij] )
mx=2；
else break；
}
maxlen=maxlenmx？ maxlen:mx；
}
for(intI=0； I
mx=0；
for(intj=0； (i-j=0) ) i j 1
if(str(I-j )==str (ij1 ) )
mx=2；
else break；
}
maxlen=maxlenmx？ maxlen:mx；
}
出局了
返回0；
}
方法四： manacher算法
预处理
在字符串的开头加上“$”符号，并在每个字符之间插入“#”。 例如，字符串ss='abac '，处理后为str='$#a#b#a#c# '。 将对处理后的字符串执行以下计算：
len数组
然后，定义表示以str[i]为中心的最长次数字符串的半径的len数组。
以上面的文字为例。 str='$#a#b#a#c# '，以str[0]为中心的最长回字符串为' $ '，其半径为1； 以str[4]为中心的最长回字符串为“#a#b#a#”，其半径为4； len序列为{1、1、2、1、4、1、2、1、2、1}。 可知len[i]-1的值是与原字符串ss对应的回文串的长度(以#为中心的是偶长的回文串，以字符为中心的是奇长的回文串)。
len数组的计算
该算法的关键在于可以在计算len矩阵时使用上述结果来优化。
如果引入变量maxright，则当前访问的所有回文子串都表示可以访问的最右边字符的位置。 同时记录与maxright对应的回文列的对称轴的位置，记为pos。
复杂度分析
考虑到p值的变化，计算过程中p只增加而不减少，但p增加到strlen(str )后，各位置len阵列的值可以很快计算出来。 所以算法的复杂性是o(n )。
#包含
#包含
#包含
用户命名空间STD；
#define N 100004
string str、ss；
int len[2*N 1]；
int main () )
{
cinss；
str='$# '；
for (未指定Inti=0； I
{
str=ss[i]；
str='# '；
}
//cout
int pos=0，p=0，j=0；
len[0]=1；
for (未指定Inti=1； I
{
j=2*pos-i；
是if(pi )
len[I]=(len[j]p-I )？ (p-i ) : ) Len[j]；
else
len[i]=1；
while (ilen [ I ]=0st r [ ilen [ I ] ]==str [ I-len [ I ] )
len[i]；
if(Ilen[I]=p ) ) ) ) )
{
pos=i；
p=i len[i]；
}
}
int ans=0；
for(intI=0； I
{
//cout
ans=(Len[I]-1=ans )？ len[i]-1:ans；
}
//cout
出局了
返回0；
}