马拉克算法因为看到了巨大的博客而受到了很大的启发。 所以省略说明。
巨大的博客
leetcode-最长回文字符串：给出字符串s，在s中找到最长的回文子串。 可以假设s的最大长度为1000。
示例1 :
键入： “babad”
输出： “bab”
请注意， “aba”也是有效的答案。
示例2 :
键入： “cbbd”
输出： “bb”
资料来源：力扣)。
链接： https://leet code-cn.com/problems/longest-palindromic-substring
版权归互联网所有。 商业转载请联系官方许可证。 非商业转载请注明出处。
原题链接
解题思想：懂马拉克就好了
交流代码： class solution (public : void init (strings，string des ) { int len=s.length )； for(intI=0； ilen； I ) { des='# '； des=s[i]； } des='# '； }stringsol(strings，string pre ) { int len=s.length )； int id； int mx=0； int p[10000]={0}； int maxlength=-1； int index=-1； for(intI=1； ilen-1； I () if ) imx ) ) p[I]=min ) p[2*id-I]，mx-i )； } else{ p[i]=1； }while(s[I{ p[i] )==s[I-p[I] ) ) p[I]； (if ) p[I]imx ) { mx=p[i] i； id=i； (if ) p[I]-1maxlength ) { maxlength=p[i]-1； 索引=I； } } string ans=' '； intstart=(索引- maxlength-1 )/2； //这里与巨大的模板代码不同，额外减少了1，但是巨大博客上的同一个for(intI=start； 开始最大长度； I ) ) { ans=pre[i]； } return ans； } stringlongestpalindrome (strings ) if ) s.length )2) { return s； } string des='$ '； init(s，des； returnsol(des，s )； }； 总结：主要是为了留下巨大的博客(Orz )