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 题目解析给定一个字符串，要求输出它最长回文子串的长度。
什么是回文子串，就是类似 baab aacaa这种中心对称的字符串。
注意，输入字符串可能包括空格，所以这里使用getline(cin,str)
思路一：中心扩展法所谓中心扩展法，就是从回文串“中心对称”这个特点来的。
我们先分析一下这个“对称”，如果是奇数长度的字符串，那么它关于最中心的那个字符对称；如果是偶数长度的字符串，它的对称线是最中心两个字符的中间画一条线（比如baab），也就是关于最中心两个字符（aa）是对称的（那两个字符是一样的）
所以中心扩展法的思路就是，把某个位置作为中间位置，向两边扩展，直到左右指针对应位置字符不等。
那么对于一个字符串，中心位置如何取，如果以每个字符作为中心，那么我们就能找到它所有长度为奇数的最长对称串的长度，以连续两个字符作为中心，救能得到所有长度为偶数的最长的对称串的长度，然后我们再二者之间取最大值即可。
文字描述比较抽象，直接看代码，挺容易理解的。
#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[0],s[1]...s[i],s[i+1],s[i+2]...s[j-2],s[j-1],s[j]...s[len-1]
如果 s[i+1,j-1] 是回文串，那么只要 s[i] == s[j]，就可以确定 s[i][j] 也是回文串
长度为1和2时的子串需单独判断
dp[i][j] 代表 s[i][j] 是不是回文子串
动态规划的核心就是由子问题状态保留，不再重新计算，对于一个长度为len的字符串，它的每个子串长度可以是 1到len，我们从小到大取出所有长度的子串进行判断。
#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; }感觉动态规划会比中心扩展更快，但提交结果是中心扩展更快，真是脑壳痛。。