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

合并回文子串

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

相关推荐

某服饰品牌 管培生 税前7500,六险一金
点赞 评论 收藏
分享
10-18 13:01
已编辑
西安理工大学 C++
小米内推大使:建议技能还是放上面吧,hr和技术面试官第一眼想看的应该是技能点和他们岗位是否匹配
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
10-12 10:48
已编辑
6面5kpi0oc的秋招小丑:邻居家老哥19届双2硕大厂开发offer拿遍了,前几天向他请教秋招,他给我看他当年的简历,0实习实验室项目技术栈跟开发基本不沾边😂,我跟他说这个放在现在中厂简历都过不了
点赞 评论 收藏
分享
1 1 评论
分享
牛客网
牛客企业服务