合并回文子串（区间dp）

时间：2024-07-27 18:33:32

链接：https://ac.nowcoder.com/acm/problem/13230
来源：牛客网

题目描述

输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可

输入描述:

第一行一个整数T(T ≤ 50)。

接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。

输出描述:

对于每组数据输出一行一个整数表示价值最大的C的价值。
示例1

输入

复制

2

aa

bb

a

aaaabcaa

输出

复制

4

5

解题思路：单独考虑合成的回文串，我们可以知道这个回文串一定是由字符串A，字符串B合成的，并且来自字符串A的字符相对位置没有变化，来自字符串B的字符的相对位置也没有变化。假设A【be1】【en1】为字符串A【i】(be1<=i<=en1)，B【be2】【en2】
为字符串B【i】（be2<=i<=en2）,如果这两个字符串能组成回文，设dp【be1】【en1】【be2】【en2】为1，回文的长度为en1-be1+1+en2-be2+1,如果不能构成回文那么dp【be1】【en1】【be2】【en2】为0。
经过分析，dp【be1】【en1】【be2】【en2】可能由四种状态转移而来。
1. dp【be1+1】【en1-1】【be2】【en2】（此时回文串的最左边的字符为A【be1】，最右边的字符为A【en1】）
2. dp【be1+1】【en1】【be2】【en2-1】 （此时回文串的最左边的字符为A【be1】，最右边的字符为B【en2】）
3.dp【be1】【en1-1】【be2+1】【en2】（此时回文串的最左边的字符为B【be2】，最右边的字符为A【en1】）
4.dp【be1】【en1】【be2+1】【en2-1】（此时回文串的最左边的字符为B【be2】，最右边的字符为B【en2】）
同时也需要注意边界的处理
#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

#include<stack>

#include<cstdio>

#include<map>

#include<set>

#include<string>

#include<queue>

using namespace std;

#define inf 0x3f3f3f3f

#define ri register int

typedef long long ll;

inline ll gcd(ll i,ll j){

	return j==0?i:gcd(j,i%j);

}

inline ll lcm(ll i,ll j){

	return i/gcd(i,j)*j;

}

inline void output(int x){

	if(x==0){putchar(48);return;}

	int len=0,dg[20];

	while(x>0){dg[++len]=x%10;x/=10;}

	for(int i=len;i>=1;i--)putchar(dg[i]+48);

}

inline void read(int &x){

    char ch=x=0;

    int f=1;

    while(!isdigit(ch)){

    	ch=getchar();

		if(ch=='-'){

			f=-1;

		}

	}

    while(isdigit(ch))

        x=x*10+ch-'0',ch=getchar();

        x=x*f;

}

int dp[55][55][55][55];

int main(){

	char st1[55],st2[55];

	int t;

	scanf("%d",&t);

	while(t--){

		scanf("%s%s",st1+1,st2+1);

		int len1=strlen(st1+1);

		int len2=strlen(st2+1);

		int ans=1;

		for(int i=0;i<=len1;i++){//回文串来自st1的长度

			for(int j=0;j<=len2;j++){//来自st2的长度

				for(int be1=1,en1=i+be1-1;en1<=len1;be1++,en1++){//起点为be1   终点 为en1

					for(int be2=1,en2=j+be2-1;en2<=len2;be2++,en2++){//起点be2 终点为 en2

						dp[be1][en1][be2][en2]=0;

						if((i+j)<=1){

							dp[be1][en1][be2][en2]=1;//边界处理

						}

						else{

							if(st1[be1]==st1[en1]&&(en1>0))dp[be1][en1][be2][en2]|=dp[be1+1][en1-1][be2][en2];

							if(st1[be1]==st2[en2]&&(en2>0))dp[be1][en1][be2][en2]|=dp[be1+1][en1][be2][en2-1];

							if(st1[en1]==st2[be2]&&(en1>0))dp[be1][en1][be2][en2]|=dp[be1][en1-1][be2+1][en2];

							if(st2[be2]==st2[en2]&&(en2>0))dp[be1][en1][be2][en2]|=dp[be1][en1][be2+1][en2-1];

						}

						if(dp[be1][en1][be2][en2]){//st1[be1]~[en1]与st2[be2]~[en2]可组成回文串

							ans=max(ans,en1-be1+en2-be2+2);

						}

					}

				}

			}

		}

		cout<<ans<<endl;

	}

	return 0;

}

　　

相关文章