给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例：
babad
输出：
bab(注意aba也是有效答案)
思路：
1、可以枚举出所有的子串，然后每次都判断该子串是否是回文，若是回文便更新最大长度，并且记录子串的开始位置和结束位置。
2、可以从第一个字符为中心向两边检查，若以k为中心 ，那么i往K的左边检测，j往右边检测。若s[i]==s[j]那么说明从i-j的子串为回文，接下来只需要判断s[i-1],s[j+1]是否相同，若相同则也是子串，并更新长度，并更新最长子串的开始位置和结束位置，直到当条件不满足s[i]==s[j]的时候，将中心点k往后移动。
方法一（暴力求解）
class Solution {
public:
bool judge(string &s, int star, int end)//判断子串是否是回文，分为奇偶两种情况
{
int median;
int length = end-star;;
if(length%2==0)
{
median = length/2;
for(int i=star; i<=star-1+median; i++)
{
if(s[i]==s[--end])
{
continue;
}
else
{
return false;
}
}
return true;
}
if(length%2!=0)
{
median = length/2;
for(int i=star; i<star+median; i++)
{
if(s[i]==s[--end])
{
continue;
}
else
{
return false;
}
}
return true;
}
}
string longestPalindrome(string s) {
int len = s.size();
string st;
int max = 0;
for(int i=0; i<len; i++)//枚举出所有子串，从开始位置到结束位置
{
for(int j=i+1; j<=len; j++)
{
if(judge(s,i,j))// 判断是否属于回文
{
if(max<j-i)//属于更新最长长度
{
max = j-i;
st = s.substr(i,j-i);
}
}
}
}
return st;
}
};
方法二：
由于我们要找一个字符作为中心点，所以要求改字符串要处理为奇数。只需要在代码中，将字符串长度变为2n+1即可，然后再还原原来实际的数组下标。例如数组babad可以处理为：#b#a#b#a#d# 然后c从元素b(下标为1处)开始为中心，此时i在下标为0处，j在下标为1处，此时要还原实际的下标，当c在奇数处的时候，i=(c-2)/2 j=(c+2)/2，所以i,j在数组babad中实际下标为0,1,则比较的是s[0],s[1]。同理若c在下标为4处的时候，此时c在偶数位置，i=(c-1)/2,j=(c+1)/2,所以实际下标为1,2则比较的是s[1],s[2]（但是这个过程中会有重复比较）。若当s[i]!=s[j]的时候，移动c的位置。
char* longestPalindrome(char* s) {
int n = strlen(s);
char *p = (char *)malloc(n+1);
int len = 2*n+1;//虚拟增加长度，使之始终为奇数
int c,j,i,star,end;
int max=0,count = 0;
for(c=1; c<len; c++)
{
if(c%2==0)//若C移到的位置为虚拟长度中不存在的位置时候，即偶数位置时候
{
i = (c-1)/2;//映射到的i,j在实际数组中的位置
j = (c+1)/2;
while((i>=0)&&(j<n)&&(s[i]==s[j]))
{
count = j-i+1;//更新最长长度
if(count>max)
{
max = count;
star = i;
end = j;
}
i = i-1;
j = j+1;
}
}
else//当中心点移动到奇数位置，在字母上的情况
{
i = (c-2)/2;//还原i,j实际下标
j = (c+2)/2;
while((i>=0)&&(j<n)&&(s[i]==s[j]))
{
count = j-i+1;
if(count>max)
{
max = count;
star = i;
end = j;
}
i = i-1;
j = j+1;
}
}
}
strncpy(p,s+star,(end-star+1));
p[end-star+1]='\0';
return p;
}