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

`Is PAT&TAP symmetric?`

Sample Output:

`11`

### 思路一：中心扩展法

```#include <iostream>
using namespace std;

// 中心扩展法
int helper(string s, int leftborder,int l,int r,int rightborder) {
// 向两端无限扩展
while(leftborder <= l && s[l] == s[r] && r <= rightborder) {
--l;++r;
}
// 已记录的有效回文串长度
return r - l - 1;
}
int main() {
string s;
getline(cin, s);
int len = s.length();
int res = 0;
for (int i = 0; i < len; ++i) {
// 以本身为中心，像左右扩展
int len1 = helper(s, 0, i, i, len - 1);
// 以自己和下一个字符为中心，向左右扩展
int len2 = helper(s, 0, i, i + 1, len - 1);
res = max(res, len1);
// 总是取更大那个
res = max(res, len2);
}
cout << res;
}```

### 思路二：动态规划

• 如果 `s[i+1,j-1]` 是回文串，那么只要 `s[i] == s[j]`，就可以确定 `s[i][j]` 也是回文串
• 长度为`1``2`时的子串需单独判断
• `dp[i][j]` 代表 `s[i][j]` 是不是回文子串

```#include<iostream>
using namespace std;

int main() {
string s;
getline(cin, s);
int len = s.length();
int res = 0;
bool dp[len][len] = {false};
int maxLen = 0;
//对于所有长度的子串
for (int len = 1; len <= s.length(); len++)
for (int i = 0; i < s.length(); i++) {
int j = i + len - 1; // i是起点,j是终点，长度是len
// 当前情况不可能，不存在从i开始长为len的子串
if (j >= s.length()) break;
//长度是1就是单个字符，满足回文
if (len == 1) dp[i][j] = true;
// 长度是2就看这两个字符是否相等
else if (len == 2) dp[i][j] = s[i] == s[j];
// 否则，如果 S[i+1,j-1] 是回文串，只要 S[i] == S[j]，S[i][j]也是回文串
else dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
// 当前串是回文串且比上一次的更长
if (dp[i][j] && len > maxLen) {
maxLen = len;
}
}
cout << maxLen;
return 0;
}```

0 条评论

• ### PAT 1001 A+B Format (20分) to_string()

Calculate a+b and output the sum in standard format -- that is, the digits must ...

• ### PAT 1021 Deepest Root (25分) 从测试点3超时到满分再到代码优化

A graph which is connected and acyclic can be considered a tree. The height of t...

• ### PAT 1015 Reversible Primes (20分) 谜一般的题目，不就是个进制转换+素数判断

A reversible prime in any number system is a prime whose "reverse" in that numbe...

• ### 2019HDU多校赛第二场 HDU 6599 I Love Palindrome String（回文树+哈希判回文）

题意：多组输入string，判断长度从1 到 len(string)的字串中有 多少 回文串，且前 一半也为回文

• ### 【LeetCode题解-005】Longest Palindrome Substring

Given a string s, find the longest palindromic substring in s. You may assume th...

• ### 你见过数组的这种骚操作吗？

注意看printf那一行，发现什么了没有？竟然有i[a]这样的操作？然后你运行一下还会发现，结果完全正常。

• ### HYSBZ 2565 最长双回文串 (回文树)

2565: 最长双回文串 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1377  Solved: 714 ...

• ### 08:Challenge 1

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列，有M次操作，每次操作是以下两种之一： （1）...

• ### 【leetcode】Two Sum

Given an array of integers, find two numbers such that they add up to a specific...