PAT 1040 Longest Symmetric String

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:

Is PAT&TAP symmetric?

Sample Output:

11

总结：这道题目还是挺简单的，直接双循环遍历所有的结果就可以了，使用reverse判断子字符串是否是对称的，如果相等，从中找到最大值

#include 
#include 
using namespace std;
 
int main(){
    string s;
    getline(cin,s);
    
    int res=0;
    for(int i=0;isize();i++){
        for(int j=1;j+i-1size();j++){
            string t=s.substr(i,j);
            string w=t;
            reverse(w.begin(),w.end());
            if(w==t && ressize())    res=w.size();
        }
    }
    printf("%d\n",res);
    return 0;
}

 依照惯例，看看大佬的代码，说不定有意想不到的收获！

果然，还真的有收获，想不到这题竟然是dp问题，好好学习

这道题题目的状态方程的计算有点像石子合并，想要计算不同区间是否是回文数字，要满足两个条件 ①区间的两个端点是相同的 ②除去端点后的子区间是回文数字，

这道题目也可以从最小区间1开始，但是需要特殊处理一下，因为当区间长度为 1 或者 2 的时候，他们是没有子区间的，只需要判断当前区间端点字母是否相等即可，其他的区间长度是需要判断子区间是否相等的（每一个较长的区间都是由子区间长度为1（区间长度为奇数时）\ 2（区间长度为偶数）的区间转移而来的）

#include 
using namespace std;
int dp[1010][1010];
int main() {
    string s;
    getline(cin, s);
    int len = s.length(), ans = 1;
    for(int i = 0; i < len; i++) {//特殊处理区间长度为1、2的情况
        dp[i][i] = 1;
        if(i < len - 1 && s[i] == s[i+1]) {
            dp[i][i+1] = 1;
            ans = 2;
        }
    }
    for(int L = 3; L <= len; L++) {
        for(int i = 0; i + L - 1 < len; i++) {
            int j = i + L -1;
            if(s[i] == s[j] && dp[i+1][j-1] == 1) {
                dp[i][j] = 1;
                ans = L;
            }
        }
    }
    printf("%d", ans);
    return 0;
}

好好学习，天天向上！

我要考研！