合并回文子串

难度：4星

定义 $d p [i] [j] [k] [p]$ 为 a 字符串的 $[i, j]$ 区间、 b 字符串的 $[k, p]$ 区间是否能构成回文子串（若能构成则 dp 值为1，反之则为0），那么显然最终答案是所有 dp 值为 1 的对应 $(j - i + 1) + (p - k + 1)$ 的最大值。

dp 方程的转移方法是：

$d p [i] [j] [k] [p] = 1$ 的充要条件是：满足以下 4 个条件任意一个即可：

① $d p [i] [j - 1] [k + 1] [p] = 1$ 且 $a [j] = b [k]$

② $d p [i + 1] [j] [k] [p - 1] = 1$ 且 $a [i] = b [p]$

③ $d p [i + 1] [j - 1] [k] [p] = 1$ 且 $a [i] = a [j]$

④ $d p [i] [j] [k + 1] [p - 1] = 1$ 且 $b [k] = b [p]$

要注意特判边界条件：长度为0或1时默认 dp 值为 1 。另外要判断字符串长度是否合法。

总复杂度 $O (n^{4})$

#include<bits/stdc++.h>
using namespace std;
int dp[55][55][55][55];
int main(){
    int t;
    cin>>t;
    while(t--){
        string a,b;
        cin>>a>>b;
        int i,jj,k,pp;
        int n=a.length(),m=b.length();
        memset(dp, 0, sizeof(dp));
        for(i=1;i<=n;i++){
            for(jj=1;jj<=m;jj++){
                if(a[i-1]==b[jj-1])dp[i][i][jj][jj]=1;
                else dp[i][i][jj][jj]=1;
            }
        }
        for(i=1;i<=n;i++){
            for(jj=1;jj<=m;jj++)dp[i][i][jj][jj-1]=dp[i][i-1][jj][jj]=1;
        }
        int res=1;
        for(jj=0;jj<=n;jj++){
            for(i=1;i<=n-jj+1;i++){
                for(pp=0;pp<=m;pp++){
                    for(k=1;k<=m-pp+1;k++){
                        int j=i+jj-1,p=k+pp-1;
                        int temp1=0,temp2=0,temp3=0,temp4=0;
                        if(pp+jj<=1){dp[i][j][k][p]=1;continue;}
                        if(pp>0&&jj>0)temp1=dp[i+1][j][k][p-1]&&(a[i-1]==b[p-1]);
                        if(pp>0&&jj>0)temp2=dp[i][j-1][k+1][p]&&(a[j-1]==b[k-1]);
                        if(j>i)temp3=dp[i+1][j-1][k][p]&&(a[i-1]==a[j-1]);
                        if(p>k)temp4=dp[i][j][k+1][p-1]&&(b[k-1]==b[p-1]);
                        
                        dp[i][j][k][p]=temp1|temp2|temp3|temp4;
                        if(dp[i][j][k][p])res=max(res,jj+pp);
                        
                    }
                }
            }
        }
        cout<<res<<endl;
    }
}

官方题解 | #合并回文子串#

合并回文子串