题目链接https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1?tpId=37&&tqId=21255&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37
题目描述
求一个串的最长回文子串？
方法一：中心对称向外扩展
- 不难发现，回文串只存在两种形式:
- 1.
AA型:即由偶数个字符组成的回文串 - 2.
ABA型:即由奇数个字符组成的回文串
AA型与ABA型回文串的最大长度即可算法执行过程如图(以样例12HHHHA举例)： i表示当前遍历的元素，假设某一时刻i遍历到途中元素时 - 1.
- 先计算能扩展的最长
AA型的长度，扩展方式即以i为中心，分别向i的左右向外直至碰到左右两边出现不相等的情况。 - 再计算能扩展的最长
ABA型的长度,扩展方式即以i和i + 1为中心，分别向i与i + 1的左右向外直至碰到左右两边出现不相等的情况。注意：ABA型只有i和i + 1代表的元素相等才可能构成回文串，否则不必扩展。 - 按这种方式计算，每个元素为中心的两种回文情况都能考虑到，故一定能求得最终解。
时间复杂度:需要遍历一遍数组，然后对每个元素执行两次向外扩展，故为O(n²)
空间复杂度：O(1)
参考代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e3 + 10;
int main()
{
string a;
cin >> a;
int ans = 1;
/*遍历每一个元素*/
for (int i = 0; i < a.size(); i ++ ) {
/*扩展计算最长AA型的回文串*/
int l = i - 1, r = i + 1;
while (l >= 0 && r < a.size() && a[l] == a[r]) {
ans = max(ans, r - l + 1); //更新答案
l -- , r ++ ;
}
/*扩展计算最长ABA型的回文串*/
l = i, r = i + 1;
while (l >= 0 && r < a.size() && a[l] == a[r]) {
ans = max(ans, r - l + 1); //更新答案
l -- , r ++ ;
}
}
cout << ans << "\n";
return 0;
}
方法二：动态规划
dp[j][i]表示索引j到索引i的子串是否是回文串,可以发现有如下三种情况可以转移：
- 1.i == j: 此时只有一个元素，是回文串，故dp[i][j] = true;
- 2.i - j = 1 && str[i] == str[j]: 此时回文，dp[i][j] = true;
- 3.i - j > 1 && str[i] == str[j] && dp[i - 1][j + 1]: dp[i][j] = true;
代码如下
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int N = 3e3 + 10;
int dp[N][N];
int main(){
string s;
cin >> s;
int n = s.size();
int maxn = 1; //最长回文子串的长度初始化为1
for (int i = 0; i < n; i++ )
for (int j = 0; j <= i; j++ )
{
/*状态转移*/
if(i == j) dp[j][i] = 1;
else if (i-j == 1) dp[j][i] = (s[i]==s[j]);
else dp[j][i] = ( s[j] == s[i] && dp[j+1][i-1] );
if(dp[j][i] && maxn < i - j + 1) maxn = i - j + 1; //更新答案
}
cout << maxn << endl;
return 0;
}
京公网安备 11010502036488号