正文
PAT甲级——A1040 Longest Symmetric String
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
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 <iostream>
#include <string>
#include <algorithm> using namespace std;
string str, t1, t2;
int res = ;
//最普通的遍历
void way1()
{
for (int i = ; i < str.length(); ++i)
{
for (int j = str.length() - ; j > i; --j)
{
t1.assign(str.begin() + i, str.begin() + j + );
t2.assign(t1.rbegin(), t1.rend());
if (t1 == t2)
res = res > t1.length() ? res : t1.length();
}
}
} //利用回文子串中心的两边相同
void way2()
{
for (int i = ; i < str.size(); ++i) {
int j;
for (j = ; i - j >= && i + j < str.size() && str[i + j] == str[i - j]; ++j);//以当前字符为回文中心查找最长回文子串
res= max(res, * j - );//更新回文子串最大长度
for (j = ; i - j >= && i + j + < str.size() && str[i - j] == str[i + + j]; ++j);//以当前字符为回文中心左侧字符查找最长回文子串
res = max(res, * j);//更新回文子串最大长度
}
} //使用动态规划
void way3()
{
int dp[][];
for (int i = ; i < str.length(); i++)
{
dp[i][i] = ;
if (i < str.length() - && str[i] == str[i + ])
{
dp[i][i + ] = ;
res = ;
}
}
for (int L = ; L <= str.length(); L++) {
for (int i = ; i + L - < str.length(); i++) {
int j = i + L - ;
if (str[i] == str[j] && dp[i + ][j - ] == ) {
dp[i][j] = ;
res = L;
}
}
}
} int main()
{
getline(cin, str);
way1();
cout << res << endl;
return ;
}
