/*
*中心扩散法:
- 如果中心字符串s是回文，那么以中心对称的字符串向左右两边扩展s1，如果左右两边
- 字符关于中心对称，那么s1也是回文，遍历所有中心点，重复上述过程，找到最长回文
- 子串。
- 中心对称分两种情况，奇数个字符以某个字母对称；偶数个字符以中间两个字符对称
- 时间复杂度：O(n^2) 空间复杂度：O(1)
http://blog.csdn.net/qustdrjhj/article/details/75427662
*/
void diffusion(char *s,int left,int right,int *sub_start,int *sub_offset)
{
while(left>=0 && s[left] == s[right])
{
left--;
right++;
}
if(*sub_offset <= ((right-1)-(left+1)))
{
*sub_offset = (right-left-2);
*sub_start = (left+1);
}
}
char* longestPalindrome(char* s) {
int i=0;
int sub_start=0;
int sub_offset=0;
char *new_s=NULL;
for(;i<strlen(s);i++)//中心点遍历
{
diffusion(s,i,i,&sub_start,&sub_offset);//奇数子串
diffusion(s,i,i+1,&sub_start,&sub_offset);//偶数子串
}
new_s = (char*)malloc((sub_offset+2)*sizeof(char));
strncpy(new_s,s+sub_start,sub_offset+1);
*(new_s+sub_offset+1)='\0';
printf("sub_start:%d sub_offset:%d\n",sub_start,sub_offset);
printf("%s\n",s+sub_start);
return new_s;
} 