PAT 1040. Longest Symmetric String (25)

Posted on Edited on In

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

这个题目首先可以想到暴力破解法，我是用动态规划做的，在时间复杂度上比暴力破解法低一个数量级，但在空间上多出了开销，典型的以空间换时间的方法 我们用dp[i, j] = 1 表示s[i]到s[j]是回文串，且有dp[i, i] = 1和if (s[i] == s[j]) dp[i, j] = dp[i + 1, j - 1]，还有if (s[i] == s[i - 1]) dp[i, i - 1] = 1这个就是比如PAAT的情况，接下来就是填dp矩阵的问题了，看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <string>
#include <iostream>

using namespace std;

int main() {
    string s;
    getline(cin, s);
    int n = s.size();
    int **len = new int *[n];
    for (int i = 0; i < n; i++) {
        len[i] = new int[n];
    }
    for (int i = 0; i < n; i++) {
        len[i][i] = 1;
        if (i > 0 && s[i] == s[i - 1]) len[i][i - 1] = 1;
    }

    int maxLen = 1;
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                len[i][j] = len[i + 1][j - 1];
                if (len[i][j] == 1) maxLen = max(maxLen, j - i + 1);
            } else len[i][j] = 0;
        }
    }
    printf("%d", maxLen);
    for (int i = 0; i < n; i++) {
        delete[] len[i];
    }
    delete[] len;
    return 0;
}