题目链接：https://oj.leetcode.com/problems/longest-palindromic-substring/
回文串即正向反向序列都一样的连续序列 如abba,abcba...
为了统一回文串的偶数情况和奇数情况，可以向串中插入不相关的字符，例如abba->#a#b#b#a#, abcba->#a#b#c#b#a#
建立数组arr[]记录主串中以第i个字符为中心的回文串向右延伸的长度(即向右覆盖长度，不包括s[i])
例如：
第一种情况：
设变量mx为当前向右最大覆盖位置下标，id为该回文串对称中心下标。在例子中，达到最右覆盖位置的为index=5,覆盖到5+arr[5]=8.所以，此时，mx=8,id=5
在计算arr[7]时(图中‘？’处i=7)，可以利用arr[0~6]的值，发现7位于以id为对称中心的覆盖范围内(图中黄色部分)。并且，i=7的对称位置id*2-i=3的覆盖范围(蓝色部分)并未超出id的覆盖范围(黄色部分)，所以，arr[7]可直接利用arr[3]的值，令arr[7]=arr[3].
另外一种情况：i未超出黄色部分，但蓝色不服超出了黄色部分。如下图：
此时，arr[7]的值至少为其关于id=5的对称位置:arr[3].所以，先为arr[7]赋初值=arr[3].然后，再从（i+arr[i]+1）,（i-arr[i]-1）分别向两端遍历即可。
最后一种情况，即i超出了黄色部分(i>=mx)，这时，只能为arr[i]赋初值arr[i]=0,并向两端遍历
代码：
class Solution
{
public:
string longestPalindrome(string s)
{
string tem;
for(int i=0;i<s.length();i++)
{
tem.push_back('#');
tem.push_back(s[i]);
}
tem.push_back('#');
s=tem;
tem.clear();
int *arr=new int[s.length()+5]; //以i为中心最长串向右延伸长度
memset(arr,0,sizeof(arr));
int id=0; //对称中心
int mx=0; //右边界
int maxid=0; //最长回文中心
for(int i=1;i<s.length();i++)
{
if(i>=mx) //在范围外
arr[i]=0;
else //在范围内
{
if(arr[id*2-i]<arr[id]+id-i)
{
arr[i]=arr[id*2-i];
continue;
}
else
arr[i]=mx-i; //肯定>or=该值
}
while(s[i-arr[i]-1]==s[i+arr[i]+1]&&i-arr[i]-1>=0&&i+arr[i]+1<s.length())
arr[i]++;
if(i+arr[i]>mx) //更新延伸最右位置
{
id=i;
mx=id+arr[id];
}
if(arr[i]>arr[maxid]) //更新最长串中心
maxid=i;
}
for(int i=maxid-arr[maxid];i<=maxid+arr[maxid];i++)
{
if(s[i]=='#')
continue;
else
tem.push_back(s[i]);
}
return tem;
}
};