每日一题-合并回文子串

合并回文子串
由于n比较小，我们可以区间dp
\(f[i][j][a][b]\)表示s[i,j]和t[a,b]能否一起构成回文子串。
\(g[i][j],h[i][j]\)分别表示s[i,j],t[i,j]能否构成回文字串。

g，h直接暴力求即可。
注意判断边界条件，也就是i=j和a=b的情况

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define A puts("Alice")
#define B puts("Bob")
using namespace std;
typedef long long ll;
const ll mo=998244353;
const int N=55;
char s[N],t[N];
int n,m,ans;
bool f[N][N][N][N],g[N][N],h[N][N];
bool v[N][N][N][N];
bool judge(int l,int r,int op){
	if (!op) {
		while (l<r){
			if (s[l]!=s[r]) return 0;
			l++; r--;
		}
		return 1;
	}
	else{
		while (l<r){
			if (t[l]!=t[r]) return 0;
			l++; r--;
		}
		return 1;
	}
}
void dg(int x,int y,int a,int b){
	if (v[x][y][a][b]) return;
	v[x][y][a][b]=1;
	
	if (x==y && a==b) {
		f[x][y][a][b]=(s[x]==t[a]);
		return;
	}
	if (x>y) {
		f[x][y][a][b]=h[a][b]; 
		return;
	}
	if (a>b) {
		f[x][y][a][b]=g[x][y]; 
		return;
	}
	bool z=0;
	
	if (s[x]==s[y] && x!=y) {
		dg(x+1,y-1,a,b); 
		z|=f[x+1][y-1][a][b];
	}
	if (s[x]==t[b]) {
		dg(x+1,y,a,b-1);
		z|=f[x+1][y][a][b-1];
	}
	if (t[a]==t[b] && a!=b) {
		dg(x,y,a+1,b-1);
		z|=f[x][y][a+1][b-1];
	}
	if (t[a]==s[y]){
		dg(x,y-1,a+1,b);
		z|=f[x][y-1][a+1][b];
	}
	f[x][y][a][b]=z;
}
int main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%s",s+1);
		n=strlen(s+1);

		scanf("%s",t+1);
		m=strlen(t+1);
		
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		memset(h,0,sizeof(h));
		memset(v,0,sizeof(v));
	
		fo(i,1,n) fo(j,i,n) g[i][j]=judge(i,j,0);
		fo(i,1,m) fo(j,i,m) h[i][j]=judge(i,j,1);
		
		ans=0;
		fo(i,1,n) fo(j,i,n) fo(k,1,m) fo(l,k,m) {
			dg(i,j,k,l);
			if (f[i][j][k][l]) ans=max(ans,(l-k+1 +j-i+1));
		}
		printf("%d\n",ans);
	}
	return 0;
}