参考答案

算法1：第一个方法当然是暴力法，外面的两层循环找到所有子串，第三层循环判断子串是否是回文。方法的时间复杂度为O(n^3)，空间复杂度为O(1)。

算法2：采用动态规划法判断子串是否是回文。开辟一个P[i][j]用来表示str[i..j]是否为回文，P[i][j]的状态转移方程如下：

当i==j时，P[i][j]=true

当i+1==j时，P[i][j]=str[i]==str[j]

其他，P[i][j]=P[i+1][j-1]&&(str[i]==str[j])

那么P[i][j]中j-i+1最大的且值为true的就是最长回文子串。这样，这个方法的时间复杂度为O(n^2)，空间复杂度为O(n^2)。比暴力法有很大的改进。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int longestPalSubstr(char *str)
{
    int n = strlen(str);
    int i, j, len, maxlen = 0, maxi = 0, maxj = 0;
    bool **P = (bool**)malloc(sizeof(bool) * n);
    for(i = 0; i < n; i++)
    {
        P[i] = (bool*)malloc(sizeof(bool) * n);
    }
    // initialize P[i][i]
    for(i = 0; i < n; i++)
    {
        P[i][i] = true;
    }
    // compute P[n][n] by length
    for(len = 2; len <= n; len++)
    {
        for(i = 0; i < n - len + 1; i++)
        {
            j = i + len - 1;
            if(len == 2)
            {
                P[i][j] = (str[i] == str[j]);
            }
            else
            {
                P[i][j] = ((str[i] == str[j]) && P[i + 1][j - 1]);
            }
        }
    }
    for(i = 0; i < n; i++) 
    {
        for(j = i; j < n; j++)
        {
            if(P[i][j] && maxlen < (j - i + 1))
            {
                maxlen = j - i + 1;
                maxi = i;
                maxj = j;
            }
        }
    }
    printf("The longest palin substr is ");
    for(i = maxi; i <= maxj; i++)
    {
        printf("%c", str[i]);
    }
    printf(", maxlen is %d\n\n", maxlen);
    return maxlen;
}
int main()
{
    char str[100];
    
    while(1)
    {
        gets(str);
        if(strlen(str) == 0) break;
        longestPalSubstr(str);
    }
    return 0;
}

算法3：第三个方法，可以从上面那个方法的状态转移方程获得启发，对于每一个回文子串可以先确定一个中心，然后向两边扩展，这样可以在时间复杂度O(n^2)，空间复杂度O(1)的情况下完成，需要注意的是，长度为奇数和偶数的中心的情况是不同的。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int longestPalSubstr(char *str)
{
    int len = strlen(str);
    int i, maxLen = 1, start = 0;
    int low, high;
    
    // 将每个字符作为中心向两边扩展判断
    for(i = 1; i < len; i++)
    {
        // 处理长度为偶数的情况
        low = i - 1;
        high = i;
        while(low >= 0 && high < len && str[low] == str[high])
        {
            if(maxLen < high - low + 1)
            {
                start = low;
                maxLen = high - low + 1;
            }
            low--;
            high++;
        }
        // 处理长度为奇数的情况
        low = i - 1; 
        high = i + 1;
        while(low >= 0 && high < len && str[low] == str[high])
        {
            if(maxLen < high - low + 1)
            {
                start = low;
                maxLen = high - low + 1;
            }
            low--;
            high++;
        }
    }
    printf("The longest palin substr is ");
    for(i = start; i < start + maxLen; i++)
    {
        printf("%c", str[i]);
    }
    printf(", maxlen is %d\n\n", maxLen);
    return maxLen;
}
int main()
{
    char str[100];
    
    while(1)
    {
        gets(str);
        if(strlen(str) == 0) break;
        longestPalSubstr(str);
    }
    return 0;
}

算法4：第四个方法采用后缀数组，将最长回文子串的问题转化为最长公共前缀的问题。具体的做法就是：将整个字符串翻转之后，拼接到原字符串后，注意用特殊字 符分开，这样问题就变成了新的字符串的某两个后缀的最长公共前缀的问题了。这个方法比较强大，很多字符串的问题都能够巧妙的解决。不过实现起来也相对比较:难，好的实现和差的实现时间复杂度相差很大。由于对后缀数组不是很清楚，未写代码，等学习了后缀数组再过来补。

算法5：第五个方法叫做Manacher算法，是一种线性时间的方法，非常巧妙。首先，我们在上面的方法中个，都要考虑回文长度为奇数或者偶数的情况。这个:方法，引入一个技巧，使得奇数和偶数的情况统一处理了。具体做法如下： abba转换为#a#b#b#a#，也就是在每一个字符两边都加上一个特殊字符。 然后创建一个新的P[i]表示，以第i个字符为中心的回文字串的半径。

例如上面的例子，对应的P如下,设S为原始字符串：

通过观察上面的表，大家可以发现P[i]-1就是实际回文字串的长度。如果知道P，遍历一次就知道最长的回文子串。可以该如何计算P呢？这是这个算法最核心的部分。

下面的讨论基本转自博客：http://www.felix021.com/blog/read.php?2040 该博客中对Manacher算法介绍得也非常好，向大家推荐。

算法引入两个变量id和mx，id表示最长回文子串的中心位置，mx表示最长回文字串的边界位置，即：mx=id+P[id]。 在这里有一个非常有用而且神奇的结论：如果mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i) 分开理解就是： 1. 如果mx - i > P[j], 则P[i]=P[j] 2. 3. 否则，P[i]  = mx - i. 4. 这两个该如何理解呢？具体的解释请看下面的两个图。 （1）当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。

（2）当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是 说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。

对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了。 理解了上面的一点，就没有问题了。

Source Code：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int longestPalSubstr(char *str)
{    
char s[100];    
int i, maxLen = 1, start = 0, j;    
int len = strlen(str);    
int mx = 0, id = 0, min;    
s[0] = '$';    s[1] = '#';    
for(i = 0, j = 2; i < len; i++, j += 2)    
{        
s[j] = str[i];        
s[j + 1] = '#';    
}    
s[j] = '\0';    
len = len * 2 + 1;    
int *p = (int *)malloc(sizeof(int) * len);    
memset(p, 0, len);    
p[0] = 1;    
for(i = 1; i < len; i++)    
{        
min = p[2 * id - i] > (mx - i) ? (mx - i) : p[2 * id - i];       
 p[i] = mx > i ? min : 1;        
 while(s[i + p[i]] == s[i - p[i]])        
 {            
 p[i]++;        
 }        
 if(i + p[i] > mx)        
 {            
 mx = i + p[i];            
 id = i;        
 }    
 }    
 for(i = 0; i < len; i++)    
 {        
 //printf("%d ", p[i]);        
 if(maxLen < p[i] - 1)        
 {  
 maxLen = p[i] - 1;            
 start = i - maxLen;       
 }    
 }    
 printf("The longest palin substr is ");    
 for(i = start; i < start + 2 * maxLen + 1; i++)    
 {        
 if(s[i] != '#')        
 {            
 printf("%c", s[i]);        
 }    
 }    
 printf(", maxlen is %d\n\n", maxLen);    
 return maxLen;
 }
int main()
{    
char str[100];        
while(1)    
{        
gets(str);        
if(strlen(str) == 0) break;        
longestPalSubstr(str);    
}    
return 0;}