2460555471
9/26/2018 - 6:06 AM

动态规划——最长回文子串

描述 给定一个字符串，寻找并输出字符串中最长回文子串。回文串即从左到右和从右到左读都一样的字符串。 如果字符串中包含多个回文子串，则返回第一个。

输入 第一行是整数n,字符串的个数(n < 20) 输出 接下来n行，每行一个字符串 字符串的长度不超过100

下面介绍动态规划的方法，使用动态规划可以达到最优的 O(n2) 复杂度。

令 dp[i][j] 表示 S[i] 至 S[j] 所表示的子串是否是回文子串，是则为 1，不是则为 0。这样根据 S[i] 是否等于 S[j] ，可以把转移情况分为两类：

若 S[i] == S[j]，那么只要 S[i+1] 至 S[j-1] 是回文子串，S[i] 至 S[j] 就是回文子串；如果S[i+1] 至 S[j-1] 不是回文子串，则 S[i] 至 S[j] 也不是回文子串。 若 S[i] != S[j]，那么 S[i] 至 S[j] 一定不是回文子串。　　　　 　　由此可以写出状态转移方程： 边界：dp[i][i]=1，dp[i][i+1] = (S[i] == S[i+1]) ? 1 : 0。

main.cpp
content_copyfile_download
/*
    最长回文子串 
*/

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

#define maxn 1010
char S[maxn];
int dp[maxn][maxn];                 

int main() {
    gets(S);                        // 输入整行字符 
    int len=strlen(S), ans=1;        // ans 记录最长回文子串长度 
    int i, j, L;        
    // 边界 
    for(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(L=3; L<=len; ++L) {            // 枚举子串长度 
        for(i=0; i+L-1 < len; ++i) {    // 枚举子串的起始节点 
            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;
}