题目描述

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;
}