最长回文子串（1）

题目二、最长回文子串

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。

输入一个字符串Str，输出Str里最长回文子串的长度。

Input

输入Str（Str的长度 <= 1000)

Output

输出最长回文子串的长度L。

输入示例

daabaac

abccbaabccbaaaaaaaaaaaaaaaaaaaaaaaaaaaa

asdfghjkltlkjhgfdsaasdfghjkl

qwertyuioppoiuytrewqqwertyuioplkjhgfdsazxcvbnmmnbvcxzasdfghjklpoiuytrewqssssssssddddddddd

ddddddkkkkkkkkkkddddddddddddkkkkkkkkkkddddddddddddkkkkkkkkkkddddddddddddkkkkkkkkkkddddddddddddkkkkkkkkkkddddddddddddkkkkkkkkkkddddddddddddkkkkkkkkkkddddddddddddkkkkkkkkkkdddddd

输出示例

176

解题思路：

1.暴力法，先写一个判断是否是回文的函数，设置两个指针i和j，i从1到len，j从i+1到len，判断i到j是不是回文串。时间复杂度为平方级，下述的代码有bug，样例2和5通不过。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #define MAXN 1010 //最大数组 
 4 int ans = 0; // 存放最大回文串的数组 
 5 bool judge(char str[], int left, int right) {
 6     int len = right - left;
 7     for (int i = 0; i < len; i++) {
 8         if (str[i] != str[len - i - 1]) { // 判断对称位置是否相等 
 9             return false;
10         }
11     }
12     if (len > ans) ans = len;  //更新最长 
13     return true;
14 }
15 
16 int main() {
17     int n = 5;
18     while (n--) {
19         char str[MAXN];
20         scanf("%s", &str);
21         int len = strlen(str);
22         ans = 0;
23         for (int i = 0; i < len - 1; i++) {
24             for (int j = i + 1; j < len; j++) {
25                 judge(&(str[i]), i, j);
26             }
27         }
28         printf("%d
", ans);
29     } 
30     return 0;
31 }

方法2：动态规划

不知道怎么解释了，直接上代码吧：

#include <cstdio>
#include <cstring>
#define MAXN 1010
char S[MAXN];
int dp[MAXN][MAXN];
int main() {
    int n = 5;
    while (n--) {
        gets(S);
        int len = strlen(S), ans = 1;
        memset(dp, 0, sizeof(dp));
        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
", ans);
    }
    return 0;
}

其实这两个都不是最优的算法，在后续我还会讲述时间复杂度为O(nlogn)的hash字符算法和最优的O(n)Manacher算法