题目链接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

题目描述

Catcher是MCA国的情报员,他工作时发现敌国会用一些对称的密码进行通信,比如像这些ABBA,ABA,A,123321,但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214 。因为截获的串太长了,而且存在多种可能的情况(abaaab可看作是aba,或baaab的加密形式),Cathcer的工作量实在是太大了,他只能向电脑高手求助,你能帮Catcher找出最长的有效密码串吗?

方法一:中心对称向外扩展

  • 不难发现,回文串只存在两种形式:
    • 1.AA型:即由偶数个字符组成的回文串
    • 2.ABA型:即由奇数个字符组成的回文串
    所以我们只需遍历每一个数时判断以当前数为中心向外扩展构成的AA型ABA型回文串的最大长度即可算法执行过程如图(以样例12HHHHA举例): i表示当前遍历的元素,假设某一时刻i遍历到途中元素时
  • 先计算能扩展的最长AA型的长度,扩展方式即以i为中心,分别向i的左右向外直至碰到左右两边出现不相等的情况。 alt
  • 再计算能扩展的最长ABA型的长度,扩展方式即以i和i + 1为中心,分别向i与i + 1的左右向外直至碰到左右两边出现不相等的情况。注意:ABA型只有i和i + 1代表的元素相等才可能构成回文串,否则不必扩展。 alt
  • 按这种方式计算,每个元素为中心的两种回文情况都能考虑到,故一定能求得最终解。

时间复杂度:需要遍历一遍数组,然后对每个元素执行两次向外扩展,故为O(n^2)

空间复杂度: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;
}

时间复杂度: O(n ^ 2)

空间复杂度: O(1)