南阳理工OJ 132 最长回文串

 

连接 ：http://acm.nyist.net/JudgeOnline/problem.php?pid=132

 

最长回文子串

时间限制：1000 ms  |  内存限制：65535 KB

难度：4

 

描述

输入一个字符串，求出其中最长的回文子串。子串的含义是：在原串连续出现的字符串片段。回文的含义是：正着看和倒着看是相同的，如abba和abbebba。在判断是要求忽略所有的标点和空格，且忽略大小写，但输出时按原样输出（首尾不要输出多余的字符串）。输入字符串长度大于等于1小于等于5000，且单独占一行(如果有多组答案，输出第一组)。

 

输入

输入一个测试数据n（1<=n<=10）；
随后有n行，每行有一个字符串。

输出

输出所要求的回文子串。

样例输入

1
Confuciuss say:Madam,I'm Adam.

样例输出

Madam,I'm Adam

 

 

 

 //思想：从字符串的第一个字符开始向两边找，找到不匹配位置，更新最长回文串
 //当然需要先对字符串处理一下

 #include<iostream>
#include<string.h>
#include<ctype.h>
#include<cstdio>
using namespace std;
const int MAX=5100;
char Yuan[MAX],s[MAX];
int p[MAX];
int main()
{
	/*freopen("1.txt","r",stdin);
	freopen("2.txt","w",stdout);*/
	int n;
	cin>>n;
	getchar();
	while(n--)
	{
		int max=0,x,y,m=0;
		gets(Yuan);
		int n=strlen(Yuan);
		for(int i=0;i<n;i++)
		{
			if(isalpha(Yuan[i]))//如果是字母
			{
				p[m]=i;//新字符串的第m个位置 存放的是原来字符串的位置
				s[m++]=toupper(Yuan[i]);  //存放新的字符串（大写的）
			}
		}
		for(int i=0;i<m;i++)//对新的字符串进行处理  从第i个位置开始向两边匹配
		{
			for(int j=0;i-j>=0&&i+j<m;j++)//奇数的情况
			{
				if(s[i-j]!=s[i+j])break;//到不匹配位置
				if(j*2+1>max)//更新最长回文串
				{
					max=j*2+1;
					x=p[i-j];//标记最长回文串两边的位置
					y=p[i+j];
				}
			}
			for(int j=0;i-j>=0&&i+j+1<m;j++)//偶数的情况
			{
				if(s[i-j]!=s[i+j+1])break;
				if(j*2+2>max)
				{
					max=j*2+2;
					x=p[i-j];
					y=p[i+j+1];
				}
			}
		}
		for(int k=x;k<=y;k++)
		{
			printf("%c",Yuan[k]);
		}
		cout<<endl;
	}

}