5. Longest Palindromic Substring

/*
*中心扩散法:

• 如果中心字符串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;  
}