每日一题：合并回文子串（区间DP）

题意

给定两个字符串，各取出一个子串接在一起，求最长回文子串的长度。

solution

先考虑普通的求最长回文子串的dp做法:

$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);
    }
  }

那么这题其实可以类比：

$dp[i][j][k][l]$ 表示a串第i个字符到第j个字符和b串第k个字符到第l个字符是否组成回文串：

往 $a[i+1]$ 到 $a[j−1]$ 和 $b[k]$ 到 $b[l]$ 构成的串的两端加上 $a[i]$ 和 $a[j]$ 两个字符：

$dp[i][j][k][l] = dp[i+1][j-1][k][l] and (a[i]==a[j])$

往 $a[i+1]$ 到 $a[j]$ 和 $b[k]$ 到 $b[l-1]$ 构成的串的两端加上 $a[i]$ 和 $b[l]$ 两个字符：

$dp[i][j][k][l] = dp[i+1][j][k][l-1] and (a[i]==b[l])$

往 $a[i]$ 到 $a[j-1]$ 和 $b[k+1]$ 到 $b[l]$ 构成的串的两端加上 $b[k]$ 和 $a[j]$ 两个字符：

$dp[i][j][k][l] = dp[i][j-1][k+1][l] and (b[k]==a[j])$

往 $a[i]$ 到 $a[j]$ 和 $b[k+1]$ 到 $b[l-1]$ 构成的串的两端加上 $b[k]$ 和 $b[l]$ 两个字符：

$dp[i][j][k][l] = dp[i][j][k+1][l-1] and (b[k]==b[l])$

实际上就是取法由原来的一种变为了四种，注意若组成的字符串长度小于2时需要直接赋值为1

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
char a[N], b[N];
bool f[N][N][N][N];
int t, n, m;
int main() {
  scanf("%d", &t);
  while (t--) {
    int res = 0;
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    for (int len1 = 0; len1 <= n; len1++)    //枚举a串的长度
      for (int len2 = 0; len2 <= m; len2++)  //枚举b串的长度
        for (int i = 1; i + len1 - 1 <= n; i++)
          for (int k = 1; k + len2 - 1 <= m; k++) {
            int j = i + len1 - 1,
                l = k + len2 - 1;  //根据左端点和长度计算右端点
            if (len1 + len2 <= 1)
              f[i][j][k][l] = 1;
            else {
              f[i][j][k][l] = 0;
              if (len1 > 1)
                f[i][j][k][l] |= (f[i + 1][j - 1][k][l] && (a[i] == a[j]));
              if (len1 && len2)
                f[i][j][k][l] |= (f[i + 1][j][k][l - 1] && (a[i] == b[l]));
              if (len1 && len2)
                f[i][j][k][l] |= (f[i][j - 1][k + 1][l] && (a[j] == b[k]));
              if (len2 > 1)
                f[i][j][k][l] |= (f[i][j][k + 1][l - 1] && (b[k] == b[l]));
            }
            if (f[i][j][k][l]) res = max(res, len1 + len2);
          }
    printf("%d\n", res);
  }
  return 0;
}