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 这就是一道模板题 AC代码：
#include <bits/stdc++.h> using namespace std; const int N = 1010; char s[N]; int dp[N][N];//存的是i到j是否为回文串 而不是回文串长度 //思想是：如果dp[i][j] = 1 就去检查dp[i+1][j-1] 如果还是回文串耐久继续检查 //倘若不检查过程中存在不满足的那就不是回文串 int main() { fgets(s, N, stdin); int ans = 1; int len = strlen(s); //先初始化边界 for(int i = 0; i < len ; i++) { dp[i][i] = 1; if(i < len-1) { if(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)//一点一点向外扩充 字符串长度为2的已经在初始化的时候判断成功 { dp[i][j] = 1; ans = L; //更新最长回文字串长度 } } } cout << ans << endl; return 0; }