9

# 参考答案

Source Code：
```#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;
}```

Source Code：
```#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;
}```

 S # a # b # b # a # P 1 2 1 2 5 2 1 2 1

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

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;}```

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题