1040. Longest Symmetric String (25)
时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue
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>
#include <string>
using namespace std;
const int MAX = 1001;
string str;
int dp[MAX][MAX], ans = 1;int main(){getline(cin, str);printf("len = %d\n", str.length());for(int i = 0; i < str.length(); i++){dp[i][i] = 1;if(i < str.length()-1){if(str[i] == str[i+1]){dp[i][i+1] = 1;ans = 2;}}}for(int l = 3; l <= str.length(); l++){for(int i = 0; i+l-1 < str.length(); i++){int j = i+l-1;if(str[i] == str[j] && dp[i+1][j-1] == 1){dp[i][j] = 1;ans = l;}}}printf("%d", ans);return 0;
}