马拉车算法
由于看了一个巨巨的博客深受启发。所以不再赘述。
巨巨的博客
leetcode-最长回文字符串：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2：
输入: “cbbd” 输出: “bb”
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-substring 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 原题链接
解题思想：
看懂马拉车即可
AC代码：
class Solution {
public:
void init(string s,string &des)
{
int len=s.length();
for(int i=0;i<len;i++)
{
des+='#';
des+=s[i];
}
des+="#";
}
string sol(string s,string pre)
{
int len=s.length();
int id;
int mx=0;
int p[10000]={0};
int maxlength=-1;
int index=-1;
for(int i=1;i<len-1;i++)
{
if(i<mx)
{
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]+i>mx)
{
mx=p[i]+i;
id=i;
}
if(p[i]-1>maxlength)
{
maxlength=p[i]-1;
index=i;
}
}
string ans="";
int start=(index-maxlength-1)/2;//这里和巨巨的模板代码不同，多减了一个1但是和巨巨博客中相同
for(int i=start;i<start+maxlength;i++)
{
ans+=pre[i];
}
return ans;
}
string longestPalindrome(string s) {
if(s.length()<2)
{
return s;
}
string des="$";
init(s,des);
return sol(des,s);
}
};
总结：
主要是为了留一下巨巨的博客（Orz）
