题目描述
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>
#include <vector>
using namespace std;
string getLCS(string str1, string str2) {
vector<vector<int>> record(str1.length(), vector<int>(str2.length()));
int maxLen = 0, maxEnd = 0;
for (int i = 0; i < str1.length(); ++i)
for (int j = 0; j < str2.length(); ++j) {
if (str1[i] == str2[j]) {
if (i == 0 || j == 0) record[i][j] = 1;
else record[i][j] = record[i - 1][j - 1] + 1;
}
else record[i][j] = 0;
if (record[i][j] > maxLen) {
maxLen = record[i][j];
maxEnd = i; //若记录i,则最后获取LCS时是取str1的子串
}
}
return str1.substr(maxEnd - maxLen + 1, maxLen);
}
int main() {
string s, r;
getline(cin, s);
r = s;
reverse(r.begin(), r.end());
string sub = getLCS(s, r);
printf("%d", sub.length());
return 0;
}
