本文主要是介绍九度OJ 1252：回文子串 （字符串处理、DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 题目描述：
-
输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
- 输入：
-
存在多组数据，每组数据一行字符串，长度不大于100。
- 输出：
-
输出回文子串的最大长度。
- 样例输入：
-
google
- 样例输出：
-
4
思路：
显而易见的思路是遍历每个数（以及每两个数）作为回文字符串的中心点（点对），然后向两边扩展验证最长回文字符串长度，超过已得到的最大值则更新。
但还有效率更高的方法，比如KMP等，我暂时还没学。
代码：
#include <stdio.h>
#include <string.h>#define M 100int main()
{int i, j, k, len, max, current;char s[M+1];while(scanf("%s", s) != EOF){len = strlen(s);max = 1;for (k=0; k<len; k++){current = 1;for (i=k-1, j=k+1; i>=0 && j<len; i--, j++){if (s[i] != s[j])break;current += 2;}max = (current > max) ? current : max;}for (k=0; k<len-1; k++){current = 0;for (i=k, j=k+1; i>=0 && j<len; i--, j++){if (s[i] != s[j])break;current += 2;}max = (current > max) ? current : max;}printf("%d\n", max);}return 0;
}
/**************************************************************Problem: 1252User: liangrx06Language: CResult: AcceptedTime:0 msMemory:912 kb
****************************************************************/这篇关于九度OJ 1252：回文子串 （字符串处理、DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
