输入

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

输出

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

输入样例

daabaac

输出样例

5

----------------------------------------------------------------------------------------------------------
可以用dp[i][j]来表示S[i]到S[j]所表示的子串是否是回文子串，此处要分两种情况讨论：
1）如果S[i] == S[j]，那么如果dp[i+1][j-1]是1，那就是回文子串，令dp[i][j]为1（dp[i][j]为1表示为回文子串，否则为0为不是回文子串）。
2）如果S[i] != S[j],那么令dp[i][j]=0，因为一定不是回文子串。
另外，面对边界的问题，dp[i][i]一定是回文子串，毕竟单个字母一定是回文的。dp[i][i+1]中，如果S[i] == S[i+1]，就是回文子串，否则不为回文子串，此处判断两个字母是否构成回文子串。
C++代码：

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int maxn = ;

char str[maxn];

int dp[maxn][maxn];

int main() {

    cin >> str;

    int len = strlen(str);

    int ans = ;

    for (int i = ; i < len; i++) {

        dp[i][i] = ;

        if (str[i] == str[i + ]) {

            dp[i][i + ] = ;

            ans = ;

        }

        else {

            dp[i][i + ] = ;

        }

    }

    int j;

    for (int L = ; L < len; L++) {

        for (int i = ; i + L -  < len; i++) {

            j = i + L - ;

            if (str[i] == str[j] && dp[i + ][j - ]) {

                dp[i][j] = ;

                ans = L;

            }

        }

    }

    cout << ans << endl;

    system("pause");

    return ;

}

巴特西

(最长回文子串线性DP) 51nod 1088 最长回文子串

输入

输出

输入样例

输出样例

最新文章

热门文章

巴特西

(最长回文子串 线性DP) 51nod 1088 最长回文子串

输入

输出

输入样例

输出样例

最新文章

热门文章

(最长回文子串线性DP) 51nod 1088 最长回文子串