回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。
Input
输入Str（Str的长度 <= 1000（第二题要求为100000）)
Output
输出最长回文子串的长度L。
Input示例
daabaac
Output示例
5
解：
#include <stdio.h> int main()
{
char s[];
while (scanf_s("%s", s, ) != EOF)
{
int max = ;
for (int i = , j, a; s[i] != ; i++)
{
for (j = ; j <= i; j++)
if (s[i + j + ] != s[i - j - ])break;
a = j * + ;
max = a > max ? a : max;
for (j = ; j <= i; j++)
if (s[i + + j] != s[i - j])
break;
a = j * ;
max = a > max ? a : max;
}
printf("%d\n", max);
}
}
后来找了一些其他的解法，比较著名的是Manacher算法，它通过插入“#”的方式将我程序中的两类讨论变为了一种情况，避免了分类讨论，同时也优化了寻找过程。
Manacher实现：
//1089 最长回文子串 V2（Manacher算法）
#include <stdio.h>
#include <string.h>
#define CLR(x,len) memset(x, '#', len) char s1[], s2[];
int p[]; int main()
{
while (scanf_s("%s", s1, ) != EOF)
{
int dis = , st = , i, len = (strlen(s1) << ) + , ans = ;
CLR(s2, len);
s2[len] = ;
for (i = ; s1[i] != ; i++) s2[i << | ] = s1[i];
i = ;
for (int temp ; i < len; i++)
{
if (i < dis) p[i] = p[(st << ) - i] > dis - i ? dis - i : p[(st << ) - i];
else p[i] = ;
while (i - p[i] > && s2[i + + p[i]] == s2[i - - p[i]]) p[i]++;
if (p[i] + i > dis)
{
dis = p[i] + i;
st = i;
}
if (s2[i + p[i]] != '#') temp = ;
else temp = ;
ans = ans > p[i] + temp ? ans : p[i] + temp;
}
printf("%d\n", ans);
}
}