看了很多大佬的代码才勉强会做。。。
大概是进行区间dp,然后枚举所有子串
因为判断c的子串是不是回文,而c的子串由a的子串和b的子串构成。
所以枚举a的子串和b的子串是否构成回文。
如下是大佬的解释:
边界情况:
当 j – i + 1 + l – k + 1 = 0 时答案是 true
当 j – i + 1 + l – k + 1 = 1 时答案是 true。
#include<iostream> #include<string> #include<vector> using namespace std; bool f[55][55][55][55]; int main(){ string a,b; int t; cin>>t; while(t--){ cin>>a>>b; a="0"+a; b="0"+b; int ans=0; int n=a.size(); int m=b.size(); for(int d1=0;d1<=n;d1++){ for(int d2=0;d2<=m;d2++){ for(int i=1,j=d1;j<n;j++,i++){ for(int k=1,l=d2;l<m;l++,k++){ if(d1+d2<=1)f[i][j][k][l]=1; else{ f[i][j][k][l]=0; if(d1>1&&a[i]==a[j])f[i][j][k][l]|=f[i+1][j-1][k][l]; if(d1&&d2&&a[i]==b[l])f[i][j][k][l]|=f[i+1][j][k][l-1]; if(d1&&d2&&b[k]==a[j])f[i][j][k][l]|=f[i][j-1][k+1][l]; if(d2>1&&b[k]==b[l])f[i][j][k][l]|=f[i][j][k+1][l-1]; } if(f[i][j][k][l])ans=max(ans,d1+d2); } } } }cout<<ans<<endl; } return 0; }