两种截然不同的问题。

最长回文子序列 (subsequence)

解决方法是动态规划。$dp[i][j]$表示区间$[i, j]$中最长的回文子序列的长度，那么可以获得递推公式
$$dp[i][j] = \begin{cases} dp[i+1][j-1] + 2 & s[i] == s[j] \\ \max(dp[i][j-1], dp[i+1][j]) & s[i] \neq s[j] \\ 1 & i == j \end{cases}$$

那还挺简单的

最长回文子串 (substring)

超暴力解法

对于每一个起始位置和结束位置，枚举所有可能的情况然后判断。时间复杂度$O(n^3)$。

暴力解法

列举每一个中心位置判断。时间复杂度$O(n^2)$。

Manacher算法

不知道哪个傻逼翻译成马拉车算法，我还以为和马+车有关系。

算法概述

1. 首先通过插入相同的字符将$n$位的字符串转换为$2n+1$位的字符串，那么所有的回文串一定是奇数长度的。
2. 维护数组$len$，$len[i]$记录以$i$为中心的最长回文串的右端到$i$的距离。$$len[i] = r – i + 1$$
3. 以$i$为中心的最长回文串的长度是$len[i] – 1$（考虑对称性）。

计算方式

从左往右计算$len$数组，假设在计算$len[i]$时，前面所有位置中右端最远的回文串的中心为$mc$，$mr = mc + len[mc] – 1$。取$i$关于$mc$的对称点$j = 2mc – i$。

1. 如果$i <= mr$
   1. 如果$i + len[j] < mr$，说明以$i$、$j$为中心的回文串关于$mc$完全对称，且是以$mc$为中心的回文串的子串。$len[i] = len[j]$。
   2. 如果$i + len[j] \ge mr$，需要对$mr$右侧的字符串进行手动匹配。
2. 如果$i > mr$，得不到信息，只能手动匹配。

算法分析

你觉得我是$O(n^2)$的？其实我是线性的！

因为$mr$只能增长不能减小，所以复杂度是$O(n)$的。（如果放在期末考试里我绝对证不出来。）

例题

HDU3068，纯模板题。

因为没有判断取$mr-mc$和$len[j]$中较小的那一个WA了一发。找了一个反例是jojojooooj。

#include <bits/stdc++.h>
using namespace std;
char ori[110005] = {};
char s[250005] = {};
int len[250005] = {};
int tot = 0, mc = 0, mr = 0, ans = 0;

int getString() {
  s[0] = '#';
  int tot = (int) strlen(ori);
  for (int i = 0; i < tot; ++i) {
    s[(i << 1) + 1] = ori[i];
    s[(i << 1) + 2] = '#';
  }
  return tot << 1;
}

int main() {
  while (scanf(" %s", ori) != EOF) {
    mc = mr = 0;
    ans = 1;
    tot = getString();
    for (int i = 0; i <= tot; ++i) {
      int j = (mc << 1) - i;
      if (i <= mr) {
        len[i] = min(mr - i + 1, len[j]);
        int pl = i - len[i], pr = i + len[i];
        while (pl >= 0 && pr <= tot && s[pl] == s[pr]) {
          len[i]++;
          pl--; pr++;
        }
      } else {
        len[i] = 1;
        int pl = i - len[i], pr = i + len[i];
        while (pl >= 0 && pr <= tot && s[pl] == s[pr]) {
          len[i]++;
          pl--; pr++;
        }
      }
      if (i + len[i] > mr) {
        mc = i;
        mr = i + len[i] - 1;
      }
      if (len[i] > ans) {
        ans = len[i] - 1;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}