回文相关算法总结及简单变形

求最长回文串

解法一：中心扩散法

过于傻逼，就是枚举中心点向两边拓展长度直到不相等。（时间复杂度 $O(n^2)$，空间复杂度 $O(1)$）

Code

#include <bits/stdc++.h>
using namespace std;
string s;

int check(int pos, int type) {
  int now, x, y;
  if (type)
    now = 0, x = pos, y = pos + 1;
  else
    now = 1, x = pos - 1, y = pos + 1;
  while (1) {
    if (x >= 0 && y < s.size() && s[x] == s[y])
      now += 2;
    else
      break;
    x--, y++;
  }
  return now;
}

int main() {
  while (cin >> s) {
    int res = 1;
    for (int i = 1; i < s.size() - 1; i++)
      res = max(res, max(check(i, 0), check(i, 1)));
    cout << res << '\n';
  }
  return 0;
}

解法二：动态规划

$dp[i][j] = 0/1 $ 表示子串 $i~j$ 是否为回文串。

那么，容易得到：$dp[i][j] = (dp[i+1][j-1]$ && $s[i]==s[j])$。

由于 $i$ 是由 $i+1$ 转移过来的，所以我们需要倒着遍历：

Code

for (int i = s.size() - 1; i >= 0; i--)
  for (int j = i; j < s.size(); j++) {
    if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
      dp[i][j] = true;
      res = max(res, j - i + 1);
    }
  }

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$

解法三：manacher

Code

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 2e6 + 5;

int p[N];
char s[N], t[N];

int manacher()
{
    int l = 0;
    t[l++] = '$';
    t[l++] = '#';
    for (int i = 0; s[i]; i++)
    {
        t[l++] = s[i];
        t[l++] = '#';
    }
    t[l++] = '@';
    int id = 0, mx = 0, index = 0, maxlength = -1;
    for (int i = 1; i < l; i++)
    {
        p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
        /// 向左右两边延伸，扩展右边界
        while (t[i + p[i]] == t[i - p[i]])
            p[i]++;
        /// 如果回文子串的右边界超过了mx，则需要更新mx和id的值
        if (i + p[i] > mx)
        {
            mx = i + p[i];
            id = i;
        }
        /// 如果回文子串的长度大于maxLength，则更新maxLength和index的值
        if (maxlength < p[i] - 1)
        {
            maxlength = p[i] - 1;
            index = i;
        }
    }
    int start = (index - maxlength) / 2; /// 记录起始位置
    return maxlength;
}

int main()
{
    while (~scanf("%s", s))
        printf("%d\n", manacher());
    return 0;
}

变形1

求最长回文子序列

solution

• 状态

  $f[i][j]$ 表示 $s$ 的第 $i$ 个字符到第 $j$ 个字符组成的子串中，最长的回文序列长度是多少。

• 转移方程

  如果 $s$ 的第 $i$ 个字符和第 $j$ 个字符相同的话

• $f[i][j] = f[i + 1][j - 1] + 2$

  如果 $s$ 的第 $i$ 个字符和第 $j$ 个字符不同的话

• $f[i][j] = max(f[i + 1][j], f[i][j - 1])$

  然后注意遍历顺序，$i$ 从最后一个字符开始往前遍历，$j$ 从 $i + 1$ 开始往后遍历，这样可以保证每个子问题都已经算好了。

• 初始化
  $f[i][i] = 1$ 单个字符的最长回文序列是 $1$

• 结果
  $f[0][n - 1]$

Code

for(int i = n - 1; i >= 0; i--) {
  dp[i][i] = 1;
  for(int j = i + 1; j < n; j++) {
    if(s[i] == s[j])
      dp[i][j] = dp[i + 1][j - 1] + 2;
    else
      dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
  }
}
return dp[0][n - 1];

变形2

插入最少的字符，使得字符串变成回文串。

solution

很直观的，答案就是原长度-最长回文子序列。考虑另一种区间dp的做法：

既然是区间dp，那么就是由小区间得到大区间，故最外层从小到大枚举长度，然后枚举左右端点。

• $dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1)$ $s[i] != s[j]$
• $dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1, dp[i + 1][j - 1])$ $s[i] == s[j]$

Code

for (int len = 2; len <= n; len++) {
    for (int l = 0; l <= n - len; l++) {
      int r = l + len - 1;
      dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1;
      if (s[l] == s[r])
        dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
    }
  }
  return dp[0][n - 1];