算法笔记 Codeup最长回文子串

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记 Codeup最长回文子串，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1863字，纯文字阅读大概需要3分钟。

内容图文

问题 A: 【字符串】最长回文子串
时间限制: 1 Sec 内存限制: 128 MB
提交: 192 解决: 92
[提交][状态][讨论版][命题人:外部导入]
题目描述
输入一个字符串，求出其中最长的回文子串。子串的含义是：在原串中连续出现的字符串片段。回文的含义是：正着看和倒着看相同。如abba和yyxyy。在判断回文时，应该忽略所有标点符号和空格，且忽略大小写，但输出应保持原样（在回文串的首部和尾部不要输出多余字符）。输入字符串长度不超过5000，且占据单独的一行。应该输出最长的回文串，如果有多个，输出起始位置最靠左的。

输入
一行字符串，字符串长度不超过5000。

输出
字符串中的最长回文子串。

样例输入
Confuciuss say:Madam,I’m Adam.
样例输出
Madam,I’m Adam
提示

样例说明：Madam,I’m Adam去掉空格、逗号、单引号、忽略大小写为MADAMIMADAM，是回文。

#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
#include <iostream>
const int maxn=5002;
char str[maxn],str1[maxn];
int main()
{
	//string str;
	int p[maxn],j = 0;
	int dp[maxn][maxn] = {0};
	int res = 0;
	gets(str);
	//const int n = str.length();
	
	for (int i = 0; i < strlen(str); i++)//将str去掉符号后复制到str1中，p[i]记录str1[i]在str中的下标
	{
		if (isalpha(str[i]) || isdigit(str[i]))
		{
            if (isalpha(str[i]))
				str1[j] = toupper(str[i]);
			else
				str1[j] = str[i];
			p[j++] = i;
		}
	}
	//初始化dp边界
	int length = strlen(str1);
	for (int i = 0; i < length-1; i++)
	{
		dp[i][i] = 1;
		if (str1[i] == str1[i + 1])
		{
			dp[i][i + 1] = 1;
			res = 2;
		}
			
	}
	dp[length - 1][length - 1] = 1;


	//动态规划开始
	int maxi = 0, maxj = 0;
	for (int L = 3; L <= length; L++)
	{
		for (int j = length-1; j-L+1>=0;j--)
		{
			int i = j - L + 1;
			if (str1[i]==str1[j]&&dp[i + 1][j-1] == 1)
			{
				dp[i][j] = 1;
				res = L;
				maxi=i;
				maxj=j;
			}
		}
	}//动态规划结束
	//判断str1中最长的回文串
	int maxij = 0;
	for (int i = 0; i < length; i++)
	{
		for (int j = length-1; j >=0; j--)
		{
			if (dp[i][j]==1&&(j-i)>maxij)
				{
					maxi = i;
					maxj = j;
					maxij = (j - i);
				}
		}
		
	}
	//
	for (int i = p[maxi]; i <= p[maxj]; i++)
		printf("%c", str[i]);
	printf("\n");
	return 0;
}

内容总结

以上是互联网集市为您收集整理的算法笔记 Codeup最长回文子串全部内容，希望文章能够帮你解决算法笔记 Codeup最长回文子串所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---