1040 Longest Symmetric String（动态规划）

左手的ㄟ右手 2024-04-08 13:05 44阅读 0赞

## 1040 Longest Symmetric String ##

### 0、题目 ###

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

### 1、大致题意 ###

给出一个字符串，要求出其中最长回文串的长度。

### 2、基本思路 ###

回文子串要么是奇数串要么是偶数串，从中间开始往两边遍历，计算长度即可。

### 3、AC代码 ###

#include<iostream>
    using namespace std;
    int main() {
        
    	string s;
    	int n = 1;
    	getline(cin,s);
    	for(int i=0; i<s.length(); i++) {
         //奇数
    		int j=0;
    		while((j+i<=s.length()-1)&&(i-j>=0)&&(s[i+j] == s[i-j]))
    			j++;
    		if(n<2*j-1) n=2*j-1;
    	}
    	for(int i=0; i<s.length()-1; i++) {
        
    		if(s[i] == s[i+1]) {
        
    			int j=0;
    			while(((j+i+1)<=s.length()-1)&&(i-j>=0)&&(s[i+j+1]==s[i-j]))
    				j++;
    			if(n<(2*j))
    				n=2*j;
    		}
    	}
    	printf("%d",n);
    	return 0;
    }

### 4、`DP`做法及思路 ###

*   d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\]表示  s \[ i \] s\[i\] s\[i\] 到  s \[ j \] s\[j\] s\[j\] 所表示的字串是否是回文字串。只有`0`和`1`
 *  递推方程：
    
     *  当`s[i] == s[j]` : `dp[i][j] = dp[i+1][j-1]`
     *  当`s[i] != s[j]` : `dp[i][j] =0`
 *  边界：`dp[i][j] = 1`, `dp[i][i+1] = (s[i] == s[i+1]) ? 1 : 0`
 *  因为`i`、`j`如果从小到大的顺序来枚举的话，无法保证更新`dp[i][j]`的时候`dp[i+1][j-1]`已经被计算过。因此不妨考虑按照字串的长度和子串的初试位置进行枚举，即第一遍将长度为`3`的子串的`dp`的值全部求出，第二遍通过第一遍结果计算出长度为`4`的子串的`dp`的值…这样就可以避免状态无法转移的问题
 *  首先初始化`dp[i][i] = 1`, `dp[i][i+1]`，把长度为`1`和`2`的都初始化好，然后从`L = 3`开始一直到 `L <= len` 根据动态规划的递归方程来判断

#include <iostream>
    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++) {
        
            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;
    }

![在这里插入图片描述][27d8e9be20f44d4cb1168b30957b3587.png]

[27d8e9be20f44d4cb1168b30957b3587.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/dd28a8fc10f84b19b8cceee0546504a4.png