求最长回文字串的长度

xiaoxiao2021-03-01  6

题目描述:

输入一个字符串,求出其中最长的回文字串的长度。子串的含义为:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和yyxyy。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应保持原样(在回文串的首部和尾部不要输出多余字符)。输入字符串长度不超过5000,且占据单独的一行。应该输出最长的回文串,如果有多个,输出起始位置最靠左的。

样例输入:Confuciuss say:Madam,I‘m Adam.

样例输出:Madam,I'm Adam.

思路分析:

1.首先将字母全部转换为大写字母(isalpha函数和toupper函数),存入另一个数组。

2.枚举回文串的起点和终点。

3.判断是不是回文串。

第一次代码可以先求出最长回文字串的长度:

#include<cstdio> #include<iostream> #include<cstring> #include<ctype.h> using namespace std; #define MAXN 5010 char buf[MAXN], s[MAXN]; int main() { int n, m = 0, max = 0; int i, j, k; fgets(buf, sizeof(s), stdin); n = strlen(buf); for(i = 0; i < n; ++i) if(isalpha(buf[i])) s[m++] = toupper(buf[i]); for(i = 0; i < m; ++i) { for(j = i; j < m; ++j) { int ok = 1; for(k = i; k <= j; ++k) { if(s[k] != s[j + i - k]) ok = 0; } if(ok && j - i + 1 > max) max = j - i + 1; } } printf("%d\n", max); }

这个程序还有一些功能没有完成,但离成功已经不远了-在实际编程中,我们经常先编写一个具备主要功能的程序,再加以完善。我们甚至可以先写一个只有输入输出功能的骨架,但是要确保它正确。这样,每次只添加一点点小功能,而且写一点就测试一下,保证它的正确性。这种方法称为迭代式开发。

现在的任务是输出这个回文串:要求原样输出,并且尽量靠左。输出靠左的条件已经满足了。我们是从左到右枚举的,且只在j - i + 1严格大于max时才更新。这样,就只剩下唯一的问题了:原样输出。

我们可以新开一个数组,用以记录s数组中字母在原数组中的起点和终点,之后输出即可。但是,题目中要求的字符可能多达5000个。则发现,效率太低。TLE。

另一种思路:

枚举回文串的中间位置i,然后不断向外扩展,直到有字符不同。(长度为奇数和偶数处理方式不同)

最终代码如下:

#include<iostream> #include<string> #include<string.h> #include<cstdio> #include<ctype.h> #include<algorithm> using namespace std; char buf[5005], res[5005], pri[5005]; int main() { //freopen("Input.txt", "r", stdin); int N; scanf("%d", &N); getchar(); while(N--) { int m = 0, len, max = 0; int i, j, x, y; gets(buf); len = strlen(buf); for(i = 0; i < len; ++i) { if(isalpha(buf[i])) { pri[m] = i; res[m++] = toupper(buf[i]); } } for(i = 0; i < m; ++i) { for(j = 0; i - j >= 0 && i + j < m; ++j) { if(res[i - j] != res[i + j]) break; if(j * 2 + 1 > max) { max = j * 2 + 1; x = pri[i - j]; y = pri[i + j]; } } for(j = 0; i - j >= 0 && i + j < m; ++j) { if(res[i - j] != res[i + j + 1]) break; if(j * 2 + 2 > max) { max = j * 2 + 2; x = pri[i - j]; y = pri[i + j + 1]; } } } for(i = x; i <= y; ++i) { printf("%c", buf[i]); } printf("\n"); } return 0; }

相关资源:带音效新年烟花动画特效-HTML-代码
转载请注明原文地址: https://www.6miu.com/read-3850001.html

最新回复(0)