九度OJ 1252：回文子串 （字符串处理、DP）
2024-09-03 09:20:44
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：387
解决：224
- 题目描述：
-
输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
- 输入：
-
存在多组数据，每组数据一行字符串，长度不大于100。
- 输出：
-
输出回文子串的最大长度。
- 样例输入：
-
google
- 样例输出：
-
4
思路：
显而易见的思路是遍历每个数（以及每两个数）作为回文字符串的中心点（点对），然后向两边扩展验证最长回文字符串长度，超过已得到的最大值则更新。
但还有效率更高的方法，比如KMP等，我暂时还没学。
代码：
#include <stdio.h>
#include <string.h> #define M 100 int 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: 1252
User: liangrx06
Language: C
Result: Accepted
Time:0 ms
Memory:912 kb
****************************************************************/
最新文章
- UEditor-从客户端(editorValue="<p>asd</p>")中检测到有潜在危险的 Request.Form 值。
- CSDN 论坛招聘区是不是有潜规则？在Cnblog招个人试试...
- cocos2d-x图片变灰或者变亮
- Django同步创建models table失败
- php 日期 - 计算2个日期的差值
- JavaEE SSH集成框架(两) struts2 本地加载dtd文件，action组态
- 常用的免费Webservice接口
- 为outlook增加“邮件召回”功能
- C++ string数据类型的实现
- Qt QFile文件读写
- git宝典—应付日常工作使用足够的指北手册
- 硬件工程师必会电路模块之MOS管应用
- 洛谷 P1223排队接水【贪心】
- Skip level 1 on 1
- 初印象至Vue路由
- tomcat警告WARNING: An attempt was made to authenticate the locked user "user"
- MySQL实例crash的案例分析
- java项目 相对路径(本项目的地址)
- POSIX是什么？
- linux 启动时文件系统错误