首页 > 代码库 > 最长回文子串
最长回文子串
时间限制:1000ms
单点时限:1000ms
内存限制:64MB
描述
小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。
这一天，他们遇到了一连串的字符串，于是小Hi就向小Ho提出了那个经典的问题：“小Ho，你能不能分别在这些字符串中找到它们每一个的最长回文子串呢？”
小Ho奇怪的问道：“什么叫做最长回文子串呢？”
小Hi回答道：“一个字符串中连续的一段就是这个字符串的子串，而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串，所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦~”
小Ho道：“原来如此！那么我该怎么得到这些字符串呢？我又应该怎么告诉你我所计算出的最长回文子串呢？
小Hi笑着说道：“这个很容易啦，你只需要写一个程序，先从标准输入读取一个整数N（N<=30)，代表我给你的字符串的个数，然后接下来的就是我要给你的那N个字符串（字符串长度<=10^6)啦。而你要告诉我你的答案的话，只要将你计算出的最长回文子串的长度按照我给你的顺序依次输出到标准输出就可以了！你看这就是一个例子。”
- 样例输入
3abababaaaaabaaacacdas
- 样例输出
753
1 #include <cstdio> 2 #include <cstring> 3 #include <string.h> 4 5 char str[1000003]; 6 7 int fast(char *str) 8 { 9 int i;10 int ans = 1;11 int e, s, t;12 13 for(i = 1; str[i]; ++i)14 {15 s = i;16 e = i;17 while(str[e + 1] == str[i]) ++e;18 i = e;19 while(str[s - 1] == str[e + 1]) --s, ++e;20 if((t = e - s + 1) > ans) ans = t;21 printf("%d\n", ans);22 }23 return ans;24 }25 26 int main()27 {28 int n;29 30 str[0] = ‘\1‘;31 scanf("%d",&n);32 while (n--) {33 scanf("%s", str + 1);34 printf("%d\n", fast(str));35 }36 return 0;37 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。