1040 Longest Symmetric String （25 分)

2019-03-17

1040 Longest Symmetric String （25 分)

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:

作者: CHEN, Yue

单位: 浙江大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

给出一字符串，求最大对称串的长度

分析

这题暴力是可以过的。i从头开始枚举，j从尾开始枚举。当s[i]==s[j]时，判断i,j之间的子串是否对称，记录下最大长度即可

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include<sstream>

using namespace std;
bool issymm(string s){
    string ss=s;
    reverse(ss.begin(),ss.end());
    return ss==s;
}
int main() {
    string s;
    getline(cin,s);
    int l=s.length();
    int max=-1;
    for(int i=0;i<l;i++){
        int flag=0;
        for(int j=l-1;j>=i;j--){
            if(s[j]==s[i])
                if(issymm(s.substr(i,j-i+1))) {
                    if(j-i+1>max) {
                        max = j - i + 1;
                        flag=1;
                    }
                }
                if(flag)
                    break;
        }
    }
    cout<<max;
}

五、其他

这题还有个动态规划的解法，非常巧妙。参考柳婼のblog