http://pat.zju.edu.cn/contests/pat-a-practise/1040
Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given "Is PAT&TAP symmetric?", the longest symmetric sub-string is "s PAT&TAP s", hence you must output 11.
Input Specification:
Each input file contains one test case which gives a non-empty string of length no more than 1000.
Output Specification:
For each test case, simply print the maximum length in a line.
Sample Input:
Is PAT&TAP symmetric?
Sample Output:
11
遍历字符串，以各个字符为对称中心的土鳖解法（这里要注意到对称序列长度有单双两种情况）：
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string s;
getline(cin, s);
int len = 1;
for (int i = 0; i < s.size(); i++){
for (int j = 0; j <= min(i, int(s.size())-1-i); j++){
string s2 = s.substr(i-j,2*j+1);
string s3 = s2;
reverse(s2.begin(), s2.end());
if (s2 == s3){
if (s2.size() > len)
len = s2.size();
}
string s4 = s.substr(i-j, 2*j+2);
string s5 = s4;
reverse(s4.begin(), s4.end());
if (s4 == s5){
if (s4.size() > len)
len = s4.size();
}
}
}
printf("%d\n", len);
return 0;
}
简单点的写法：
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string s;
getline(cin, s);
int len = 0;
for (int i = 0; i < s.size(); i++){
int m = 0, n = 0, len1 = 0, len2 = 0;
while(i - n >= 0 && i + n < s.size() && s[i - n] == s[i + n]){
len1 = 2 * n + 1;
n++;
}
if (len1 > len) len = len1;
while(i + 1 < s.size() && s[i] == s[i + 1] && i - m >= 0 && i + m + 1 < s.size() && s[i - m] == s[i + 1 + m]){
len2 = 2 * m + 2;
m++;
}
if (len2 > len) len = len2;
}
printf("%d\n", len);
return 0;
}
网上看到的动态规划解法：
using namespace std;
int main()
{
string s;
getline(cin,s); //读取包含空格的一行
int max=1;
int n=s.size(); //字符串长度
bool flag[1005][1005]; //s[i]~s[j]是否是回文，1是，0不是
int i,j;
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
flag[i][j]=true;
for(j=1;j<n;j++)
{
for(i=0;i<j;i++)
{
flag[i][j]=false;
if(s[i]==s[j]&&flag[i+1][j-1]==true)
{
flag[i][j]=true;
if(j-i+1>max)
max=j-i+1;
}
}
}
cout<<max;
return 0;
}