题目要求
对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。
输入格式：
输入在一行中给出长度不超过1000的非空字符串。
输出格式：
在一行中输出最长对称子串的长度。
输入样例：
Is PAT&TAP symmetric?
输出样例：
11
解题思路
这道题可以采用中心扩展算法，并结合动态规划来实现。具体思路如下：
首先可以枚举字符串中所有的中心位置，将其看做是一个回文字符串的中间位置。对于每个中心位置，分别向两端扩展，直到无法再扩展为止。
在扩展的过程中，记录回文字符串的起始和结束位置，以及当前回文串的长度。
如果当前回文串的长度大于已有最长回文子串长度，则更新最长回文子串的长度。
如果输入的字符串长度小于等于1，则其本身就是回文串，直接输出字符串长度即可。
最终得到最长回文子串的长度，即为输出结果。
代码
#include <iostream> #include <cstring> using namespace std; const int N = 1010; int dp[N][N]; int main() { string s; getline(cin, s); // 输入字符串 int n = s.size(), ans = 0; // 如果长度小于等于1，直接输出长度即可 if (n <= 1) { cout << n << endl; return 0; } // 初始化：所有长度为1的子串都是回文串 for (int i = 0; i < n; i++) dp[i][i] = true; // 遍历字符串，先枚举区间长度，再枚举起始位置 for (int len = 2; len <= n; len++) for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; // 区间右边界 if (s[i] == s[j]) // 如果左右边界相同 { if (len == 2 || dp[i + 1][j - 1]) // 如果区间长度为2或左右边界内部也是回文串 dp[i][j] = true; } if (dp[i][j]) // 记录最长回文子串长度 ans = max(ans, len); } cout << ans << endl; // 输出结果 return 0; }
dp[i][j] 表示从第 i 个字符到第 j 个字符是否为回文串。
在代码实现中，先对所有长度为1的子串进行初始化，然后依次枚举区间长度和起始位置来填充整个 dp 数组。如果当前区间左右边界相同，则需要判断左右边界内部是否也是回文串。最终，我们可以找到最长回文子串的长度并输出即可。
总结
本文使用中心扩展算法，并结合动态规划来解题，读者可躬身实践。
我是秋说，我们下次见。
