题解 | 合并回文子串

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

const int N = 60;
int dp[N][N][N][N];

void solve(){
    
    string str1,str2;
    cin>>str1>>str2;

    int len1 = str1.size();
    str1 = ' ' + str1;
    int len2 = str2.size();
    str2 = ' ' + str2;
	
    memset(dp,0,sizeof dp);

	int ans = 1;
	for(int a = 0;a<=len1;a++){
		for(int i = 1;i+a-1<=len1;i++){
			for(int b = 0;b<=len2;b++){
				for(int j = 1;j+b-1<=len2;j++){
					
					int k1 = i + a -1,k2 = j+b-1;
					if(a+b<=1) dp[i][k1][j][k2] = 1;
					if(str1[i]==str1[k1]){
						dp[i][k1][j][k2] |= dp[i+1][k1-1][j][k2];
					} 
					if(str2[j]==str2[k2]) {
						dp[i][k1][j][k2] |= dp[i][k1][j+1][k2-1];
					}
					if(str1[i]==str2[k2]){
						dp[i][k1][j][k2] |= dp[i+1][k1][j][k2-1];
					} 
					if(str2[j]==str1[k1]){
						dp[i][k1][j][k2] |= dp[i][k1-1][j+1][k2];
					} 
					
					if(dp[i][k1][j][k2])ans = max(ans,a+b);
				}
			}
		}
	} 	

	cout<<ans<<"\n";

}

int main(){
    int t;cin>>t;
    while(t--) solve();
    return 0;
}

如果区间长度只有1，那么该区间回文长度为1，然后判断两个字符串的前缀和后缀是否相等，并且前面是否构造成功，如果有其中一个满足，那么就和答案比大小

#牛客春招刷题训练营#https://www.nowcoder.com/discuss/727521113110073344