题解 | #最长回文字符串#

合并回文子串

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;
}
全部评论

相关推荐

1 1 评论
分享
牛客网
牛客企业服务