题解 | #合并回文子串#

//字符串c中价值最大的子串一定是由A中的某个子串和B中的某个子串组成的。
//那么对于已知的dp[i][j][k][l]的状态，可以转移到取A字符串两边放到C字符串两边。
//可以是取B字符串两边放到C字符串两边。
//可以是取A字符串的右边和B字符串的左边来放到C字符串的两边
//可以是取A字符串左边和B字符串的右边来放到C字符串的两边。
//那么状态转移方程为：
// if (a[i]==a[j]) dp[i][j][k][l] |= dp[i+1][j-1][k][l];
// if (b[k]==b[l]) dp[i][j][k][l] |= dp[i][j][k+1][l-1];
// if (a[i]==b[l]) dp[i][j][k][l] |= dp[i+1][j][k][l-1];
// if (a[j]==b[k]) dp[i][j][k][l] |= dp[i][j-1][k+1][l];
#include <bits/stdc++.h>

using namespace std;
const int maxn = 55;
int dp[maxn][maxn][maxn][maxn];
string a, b;

int main() {
    int T;
    cin>>T;
    while (T--) {
        cin>>a>>b;
        a = " "+a;b = " "+b;
        memset(dp, 0, sizeof(dp));
        int ans = 1;
        for (int x=0;x<=a.size()-1;x++) {
        	for (int y=0;y<=b.size()-1;y++) {
        		for (int i=1;i+x-1<=a.size()-1;i++) {
        			for (int k=1;k+y-1<=b.size()-1;k++) {
        				int j = i+x-1, l = k+y-1;
        				if (x+y<=1) {
        					dp[i][j][k][l] = 1;
						}
                        else {
//                             if (x>=3)
                            if (a[i]==a[j]) dp[i][j][k][l] |= dp[i+1][j-1][k][l];
                            if (b[k]==b[l]) dp[i][j][k][l] |= dp[i][j][k+1][l-1];
//                             if (x&&y) {
                                if (a[i]==b[l]) dp[i][j][k][l] |= dp[i+1][j][k][l-1];
                                if (a[j]==b[k]) dp[i][j][k][l] |= dp[i][j-1][k+1][l];
//                            }
                        }
//						
						if (dp[i][j][k][l]) {
							ans = max(ans, x+y);
						}
					}
				}
			}
		}
        cout<<ans<<endl;
    }
    
    
    return 0;
}