PAT A1040 . 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "stdio.h"
//#include "math.h"
#include "string.h"
//#include "iostream"
//#include "stdlib.h"
//#include "vector"
//#include "set"
//#include "map"
//#include "stack"
//#include "queue"
#include "algorithm"
using namespace std;

const int maxn = 1010;
char S[maxn];
int dp[maxn][maxn];

int main(){
gets(S);
int len = strlen(S), ans = 1;
memset(dp, 0, sizeof(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) {
dp[i][j] = 1;
ans = L;//更新最长回文子串长度
}
}
}
printf("%d\n", ans);
return 0;
}