【每日一题】合并回文子串

原题链接：

https://ac.nowcoder.com/acm/problem/13230

题目大意：

给定两个字符串，不改变两个字符串字符的顺序进行组合，得到一个新字符串，求新字符串中最长的回文子串的长度。

解题思路：

建立一个四维dp数组，该数组是用来判断取组成的字符串是否能构成回文子串。在判断时首尾可以有四种取法：。判断时先判断首尾字符是否相等，在判断去除首尾后的字符串是否能构成回文串。如，首尾分别为，先判断是否等于,如果等于在判断，是否为，如果为1，那么。（想不出有什么简单的初始化方法，所以代码中，初始化复杂，并且含有各种特殊情况的特判）。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(i=a;i<=b;i++)
#define debug(a) cout<<#a<<":"<<a<<endl;
const int INF=1e9+7;
const int N=1e6+7;
const int mod=1e9+7;
int maxn,minn;
int T,n;
char a[N],b[N];
int dp[55][55][55][55];

int main(){
    int len1,len2;
    cin>>T;
    while(T--){
        memset(dp,0,sizeof(dp));
        maxn=0;
        scanf("%s%s",a+1,b+1);
        len1=strlen(a+1);
        len2=strlen(b+1);
        for(int i=len1;i>=1;i--){        //只在a字符串中找回文子串 
            for(int j=i;j<=len1;j++){
                if(i==j){
                    dp[i][j][0][0]=1;
                }
                else if(i==j-1){
                    if(a[i]==a[j]){
                        dp[i][j][0][0]=1;
                    }
                }
                else{
                    if(a[i]==a[j]&&dp[i+1][j-1][0][0]){
                        dp[i][j][0][0]=1;
                    }
                }
                maxn=max(maxn,dp[i][j][0][0]);
            }
        }
        for(int i=len2;i>=1;i--){        //只在b字符串找回文子串 
            for(int j=i;j<=len2;j++){
                if(i==j){
                    dp[0][0][i][j]=1;
                }
                else if(i==j-1){
                    if(b[i]==b[j]){
                        dp[0][0][i][j]=1;
                    }
                }
                else{
                    if(b[i]==b[j]&&dp[0][0][i+1][j-1]){
                        dp[0][0][i][j]=1;
                    }
                }
                maxn=max(maxn,dp[0][0][i][j]);
            }
        }
        for(int i=len1;i>=1;i--){        //i的顺序要从大到小，因为算dp[i]需要用到dp[i+1],下面同理 
            for(int j=i;j<=len1;j++){
                for(int k=len2;k>=1;k--){
                    for(int l=k;l<=len2;l++){
                        if(i!=j){        //当i==j时就无法构成i,k,l,j这种形式 
                            if(i==j-1){
                                if(a[i]==a[j]&&dp[0][0][k][l]){
                                    dp[i][j][k][l]=1;
                                }
                            }
                            else{
                                if(a[i]==a[j]&&dp[i+1][j-1][k][l]){
                                    dp[i][j][k][l]=1;
                                }
                            }
                        }
                        if(k!=l){        //当k==l时就无法构成k,i,j,l这种形式
                            if(k==l-1){
                                if(b[k]==b[l]&&dp[i][j][0][0]){
                                    dp[i][j][k][l]=1;
                                }
                            }
                            else{
                                if(b[k]==b[l]&&dp[i][j][k+1][l-1]){
                                    dp[i][j][k][l]=1;
                                }
                            }
                        }
                        //接下来是判断能否构成i,j,k,l与k,l,i,j这两种形式 
                        if(i==j&&k==l){
                            if(a[i]==b[k]){
                                dp[i][j][k][l]=1;
                            }
                        }
                        if(i==j&&k!=l){
                            if(a[i]==b[l]&&dp[0][0][k][l-1]){
                                dp[i][j][k][l]=1;
                            }
                            if(a[i]==b[k]&&dp[0][0][k+1][l]){
                                dp[i][j][k][l]=1;
                            }
                        }
                        if(i!=j&&k==l){
                            if(a[i]==b[l]&&dp[i+1][j][0][0]){
                                dp[i][j][k][l]=1;
                            }
                            if(a[j]==b[l]&&dp[i][j-1][0][0]){
                                dp[i][j][k][l]=1;
                            }
                        }
                        if(i!=j&&k!=l){
                            if(a[i]==b[l]&&dp[i+1][j][k][l-1]){
                                dp[i][j][k][l]=1;
                            }
                            if(b[k]==a[j]&&dp[i][j-1][k+1][l]){
                                dp[i][j][k][l]=1;
                            }
                        }
                        if(dp[i][j][k][l]==1){
                            maxn=max(maxn,j-i+1+l-k+1);
                        }
                    }
                }
            }
        }
        cout<<maxn<<endl;
    }
    return 0;
}