字符串 模板 模拟

最长回文子序列

给定一个字符串 s , 求 s 的最长回文子序列

1 模拟暴力法

• 通过一个二维数组遍历原字符串的所有子串
• 逐一判断该子串是否为回文串
• 更新最长子串

#pragma GCC optimize(3)
#include <bits/stdc++.h>
//#define int LL
#define endl '\n'
#define size_t int
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long LL;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
 
string huiwen(const string &s, int back, int front)
{
    int idx_b = back;
    int idx_f = front;
    while (idx_b > idx_f) {
        if (s[idx_f] != s[idx_b]) {
            return s.substr(0,1);
        }
        idx_f++;
        idx_b--;
    }
    string res;
    for (size_t i = front; i <= back; i++) {
        res += s[i];
    }
    return res;
}
 
signed main()
{
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s;
    cin >> s;
    string ans = "";
    if(s.size() <= 1){
        cout << s;
    }
    for (size_t i = 0; i < s.size(); i++) {
        for (size_t j = i + 1; j < s.size(); j++) {
            string temp = huiwen(s, j, i);
            ans = (temp.size() > ans.size() ? temp : ans);
        }
    }
    cout << ans;
    return 0;
}

这个算法的复杂度来到了惊人的$O(n^3)$,令人汗颜，数据量在$10^3$就能直接让OJ爆TLE

2 中心扩展算法

中心算法的三个核心步骤

• 1.选择中心：对于一个长度为 $n$ 的字符串，其拥有 $2n-1$ 个中心结点（即长度为奇数的回文子串结点有$n$个，长度为偶数的回文子串的结点有$n-1$个
• 2.扩展回文：对于每个选定的中心，尝试向两边扩展，直到无法形成回文为止
• 3.更新结果：在每次成功扩展后，计算当前回文的长度，并与已知的最大回文长度进行比较。如果更长，则更新最大回文及其起始位置

//#pragma GCC optimize(3)
#include <bits/stdc++.h>
//#define int LL
#define endl '\n'
#define size_t int
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long LL;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
 
int expandAroundCenter(const string &s, int left, int right)
{
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}
 
string longestPalindrome(const string &s)
{
    if (s.empty()) return "";
    int start = 0;
    int end = 0;
    for (size_t i = 0; i < s.size(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = max(len1, len2);
        if (len > end - start) {
            end = i + len / 2;
            start = i - (len - 1) / 2;
        }
    }
    return s.substr(start, end - start + 1);
}
 
signed main()
{
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s;
    cin >> s;
    cout << longestPalindrome(s) << endl;
    return 0;
}

此时时间复杂度已经降至 $O(n^2)$ ，空间复杂度降低至$O(1)$ ,已经绝杀大部分算法

3 Manacher’s Algorithm

很抱歉没能让manacher大人尽兴 ——by 中心扩展算法

• Manacher’s Algorithm(马拉车算法)是一种高效解决最长回文子串的算法，其提供一个$O(n)$复杂度下的方法来实现对回文子序列的查找

  • 核心思想
  • 回文串的对称性： 假设已经计算出了以某个位置为中心的回文串的半径（即该回文串两边的最大扩展长度），那么与其对称的部分的回文半径也可以直接推算出来
  • 预处理：将原字符串进行预处理，以避免处理奇数长度和偶数长度回文的不同情况。通常的做法是在每个字符之间插入一个特殊字符（如 #），并在字符串的开头和结尾添加不同的特殊字符（如 ^ 和 $）。这样处理后的字符串长度一定是奇数，且不会出现冲突。
  • 动态维护最远回文边界：在扩展时，维护一个“右边界” R 和一个“中心” C，C 代表回文串的中心位置，R 代表回文串的最右边界。当当前处理的位置 i 位于 R 的范围内时，可以利用已知的对称性质来减少计算。

  //#pragma GCC optimize(3)
  #include <bits/stdc++.h>
  //#define int LL
  #define endl '\n'
  #define size_t int
  #define all(v) v.begin(), v.end()
  using namespace std;
  typedef long long LL;
  typedef vector<int> vint;
  typedef vector<vint> vvint;
  typedef vector<string> vstr;
  typedef pair<int, int> pii;
  typedef vector<pii> vpii;
   
  //预处理
  string preprocess(const string &s)
  {
      string t = "^";
      for (char c : s) {
          t += "#" + string(1, c);
      }
      t += "#$";
      return t;
  }
   
  string longestPalindrome(const string &s)
  {
      string T = preprocess(s);
      int n = T.size();
      vector<int> P(n, 0); //P[i] 记录以 t[i] 为中心的回文半径
      int C = 0, R = 0;    //C 是回文中心，R 是回文串的最右边界
      for (size_t i = 1; i < n - 1; i++) {
          // 确定对称位置
          int Mirror = 2 * C - i;
          if (i < R) {
              P[i] = min(P[Mirror], R - i);
          }
          // 尝试扩展边界
          while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) {
              P[i]++;
          }
          // 如果当前回文串扩展超过了 R，更新中心和右边界
          if (i + P[i] > R) {
              C = i;
              R = i + P[i];
          }
      }
      // 找到最长的回文子串
      int maxLen = 0;
      int Centerindex = 0;
      for (size_t i = 0; i < n - 1; i++) {
          if (P[i] > maxLen) {
              maxLen = P[i];
              Centerindex = i;
          }
      }
      // 构造回文串
      int start = (Centerindex - maxLen) / 2;
      return s.substr(start, maxLen);
  }
   
  signed main()
  {
      //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
      string s;
      cin >> s;
      cout << longestPalindrome(s) << endl;
      return 0;
  }