PTA甲级——1040

1040 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:

1
Is PAT&TAP symmetric?

Sample Output:

1
11

思路

​ 非常经典的一种类型的题目，寻找回文字串长度最大值类型题目，一般有O(n^3)、O(n^2)、O(n)、O(nlogn)四种经典办法来写，这里数据量为1000,因此使用第二种写法就ok了。

​ 如果想看其他写法，可以看看这篇文章最长回文子串的四种解法

代码

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 <iostream>
#include <algorithm>

using namespace std;

int calc(string s,int l, int r) {
    int count = 0;
    int len = s.size();
    while (l >= 0 && r < len && s[l] == s[r]) {
        l--;
        r++;
    }
    return r - l - 1;
}

int main(){
    string s;
    while (cin >> s) {
        int len = s.length(), Max = 0;
        if (len <= 1) {
            cout << len << '\n';
            continue;
        }
        for (int i = 0; i < len; i++) {
            int ans, res;
            ans = calc(s, i, i);  
            res = calc(s, i, i + 1);
            Max = max(Max, max(res, ans));
        }
        cout << Max << '\n';
    }
    
    return 0;
}