天梯赛L2-008 最长对称子串 (字符串处理)

对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定"Is PAT&TAP symmetric?",最长对称子串为"s PAT&TAP s",于是你应该输出11。

输入格式:

输入在一行中给出长度不超过1000的非空字符串。

输出格式:

在一行中输出最长对称子串的长度。

输入样例:

Is PAT&TAP symmetric?

输出样例:

11

分析:

刚开始的时候觉得就是暴力循环下去,取最大值,然而 不用想肯定超了,然后就有一种比较巧妙的方法。

这个子串是对称的应该有两种对称的方式,一种是关于中间的那个字符对称,一种就是关于中间的两个相同的字符对称。

关于中间一个字符对称

例如abcdedcba,这个字符串是关于中间字符e对称的,我们只需要在找到中间字符e的时候,分别将左面的第i个于右面的第i个进行比较相等即可。d——d,c——c,b——b,a——a

关于中间两个字符对称

例如abcdeedcba,这个字符串是关于中间的两个字符ee对称的,我们在找到e的时候不能够简单的像上面一样向左向右比较,我们应该先确定e与他后面的另一个字符e是一样的,然后再分别向左向右比较。首先比较e——e,然后d——d,c——c,b——b,a——a

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
using namespace std;
int main()
{
char a[1009];
gets(a);//所需要读入的字符串中可能有空格,则一定要用get()读进去
int k=strlen(a);
int num=0;
int max=0;
for(int i=0;i<k;i++)
{
/*
对称的串有两种形式,
一:这个串的长度为奇数个,即他有一个对称的字符
二:这个串的长度有偶数个,他是关于中间的两个相等的字符对称的
*/
//如果对称的串长度为奇数,我们就可以直接把中间的这个字符取出来,向左向右分别比较
num=1;
for(int j=1;j<k;j++)//依次为左右的第i个字符
{
if(i-j<0||i+j>=k||a[i-j]!=a[i+j])
break;
num+=2;
}
if(num>max)
max=num;
//如果对称串的长度为偶数个,我们不能把当前的字符直接取出来,要比较他和他的后一个相等,然后再向左向右依次比较
num=0;
for(int j=1;j<k;j++)
{
if(i-j+1<0||i+j>=k||a[i-j+1]!=a[i+j])
break;
num+=2;
}
if(num>max)
max=num;
}
printf("%d\n",max);
return 0;
}
上一篇:js数组排序 reverse()和sort()方法的使用


下一篇:nodejs怎么同步从一个数据库查询函数中返回一个值