“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
动态规划解法(O(n²)):
令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是则为1，不是为0。
根据S[i]是否等于S[j]，可以把转移情况分为两类：
(1) 若S[i]==S[j]，那么只要S[i+1]至S[j-1]是回文子串，S[i]至S[j]就是回文子串。
(2) 若S[i]!=S[j]，S[i]至S[j]一定不是回文子串。
1 #include <cstdio>
2 #include <cstring>
3 using namespace std;
4
5 const int maxn = 1010;
6 char s[maxn];
7 int dp[maxn][maxn];
8 int main() {
9
10 memset(dp, 0, sizeof(dp));
11 gets(s);
12 int len = strlen(s),ans = 1;
13 for (int i = 0; i < len; i++) {
14
15 dp[i][i] = 1;
16 if (i+1<len&&s[i + 1] == s[i]) {
17 dp[i][i + 1] = 1;
18 ans = 2;
19 }
20 }
21
22 for (int L = 3; L <= len; L++) {
23 for (int i = 0; i + L-1 < len; i++) {
24 int j = i + L - 1;
25 if (s[i] == s[j] && dp[i + 1][j - 1] == 1) {
26 dp[i][j] = 1;
27 ans = L;
28 }
29
30 }
31 }
32
33 printf("%d
", ans);
34 return 0;
35 }