L2-008. 最长对称子串

时间限制
100 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越

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

输入格式:

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

输出格式:

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

输入样例:

Is PAT&TAP symmetric?

输出样例:

11

思路:由于数据比较弱,就不考虑manacher算法啦(我不会)。。

不过可以提供一下这个算法的讲解http://www.cnblogs.com/biyeymyhjob/archive/2012/10/04/2711527.html

 #include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
getline(cin,s);
int tmp,max=;
for(int i=; i<s.size(); i++)
{
tmp=;
for(int j=; j<=s.size(); j++)
{
if(i-j<||i+j>s.size()) break;
if(s[i-j]!=s[i+j]) break;
tmp+=;
}
if(tmp>max)
max=tmp;
tmp=;
for(int j=; j<=s.size(); j++)
{
if(i-j+<||i+j>s.size()) break;
if(s[i-j+]!=s[i+j]) break;
tmp+=;
}
if(tmp>max)
max=tmp; }
cout<<max<<endl;
return ;
}
04-22 19:16