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

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

串的子串：一个串的子串指此（字符）串中连续的一部分字符构成的子（字符）串例如 abc 这个串的子串：空串、a、b、c、ab、ac、bc、abc

 收起  

输入

输入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 = 1002; char str[maxn]; int dp[maxn][maxn]; int main() { cin >> str; int len = strlen(str); int ans = 1; for (int i = 0; i < len; i++) { dp[i][i] = 1; if (str[i] == str[i + 1]) { dp[i][i + 1] = 1; ans = 2; } else { dp[i][i + 1] = 0; } } int j; for (int L = 3; L < len; L++) { for (int i = 0; i + L - 1 < len; i++) { j = i + L - 1; if (str[i] == str[j] && dp[i + 1][j - 1]) { dp[i][j] = 1; ans = L; } } } cout << ans << endl; system("pause"); return 0; }

 

转载于:https://www.cnblogs.com/Weixu-Liu/p/10712024.html

相关资源：JAVA上百实例源码以及开源项目