1040 Longest Symmetric String（动态规划）

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?
1

Sample Output:

11
1

1、大致题意

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

2、基本思路

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

3、AC代码

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4、DP做法及思路

• $dp[i][j]$表示 $s[i]$ 到 $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 
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;
}
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