题解 | #最长回文字符串#
合并回文子串
http://www.nowcoder.com/practice/2f43728b46744546b4ad7f4f0398054f
最长回文字符串
#include<stdio.h>
int main()
{
char A[55],B[55];
int n,max=0;
scanf("%d",&n);
for(int q=0;q<n;++q)
{
scanf("%s%s",A+1,B+1);
max=0;
int dp[52][52][52][52]={0};
memset(dp,0,sizeof(dp));
for(int d1=0;d1<=strlen(A+1);++d1)
{
for(int d2=0;d2<=strlen(B+1);++d2)
{
for(int i=1,j=d1;j<=strlen(A+1);++i,++j)
{
for(int k=1,l=d2;l<=strlen(B+1);++k,++l)
{
if(d1+d2<=1) dp[i][j][k][l]=1;
else{
//dp[i][j][k][l]=0;
if(A[i]==A[j] && d1>1) dp[i][j][k][l] |= dp[i+1][j-1][k][l];
if(B[k]==B[l] && d2>1) dp[i][j][k][l] |= dp[i][j][k+1][l-1];
if(A[i]==B[l] && d1 && d2) dp[i][j][k][l] |= dp[i+1][j][k][l-1];
if(A[j]==B[k] && d1 && d2) dp[i][j][k][l] |= dp[i][j-1][k+1][l];
}
if(dp[i][j][k][l])
max = max>(d1+d2)?max:(d1+d2);
}
}
}
}
printf("%d\n",max);
}
return 0;
}