【每日一题】合并回文子串

戳我传送
题意:
图片说明
思路:
区间dp,图片说明 表示a串的第i个字符到第j个个字符和b串第k个字符到第l个字符组成的串能否构成回文串,求法通过分解代码的形式分析,因为这个思路对我来说有点难。

for(int len1=0;len1<=n;++len1)
for(int len2=0;len2<=m;++len2)
for(int i=1;i+len1-1<=n;++i)
for(int k=1;k+len2-1<=m;++k)

这里是枚举区间长度和起点,然后根据区间长度和起点可以退出终点,len1<=n很好理解,因为终点j=i+len1-1不能大于n,所以i+len1-1<=n,len2也是一个道理。

int j=i+len1-1,l=k+len2-1;

计算a串区间的右端点j,b串区间的右端点l,特别当长度为0时,右端点=左端点-1。

if(len1+len2<=1) f[i][j][k][l]=true;
else {
    f[i][j][k][l]=false;
    if(len1>1) f[i][j][k][l] |= (f[i+1][j-1][k][l]&&a[i]==a[j]);
    if(len1 && len2) f[i][j][k][l] |= (f[i+1][j][k][l-1] && (a[i]==b[l]));
    if(len1 && len2) f[i][j][k][l] |= (f[i][j-1][k+1][l] && (a[j]==b[k]));
    if(len2>1) f[i][j][k][l] |= (f[i][j][k+1][l-1] && (b[k]==b[l]));
}
if(len1+len2<=1) f[i][j][k][l]=true;

如果只有a串提供一个字符、b串提供一个字符或者都不提供字符,那么一定是回文串,这是边界情况。

if(len1>1) f[i][j][k][l] |= (f[i+1][j-1][k][l]&&a[i]==a[j]);
if(len2>1) f[i][j][k][l] |= (f[i][j][k+1][l-1]&&b[k]==b[l]);

图片说明图片说明 ,因为回文串可以是a、b串交叉形成的,也就是可能a、b选出某个区间的字符组成回文串后,两端加上a串该区间的前一个字符和后一个字符,且这两个字符相等,那么新形成的串还是回文串。第二行和第一行一样的就不讲了。

if(len1 && len2) f[i][j][k][l] |= (f[i+1][j][k][l-1] && (a[i]==b[l]));
if(len1 && len2) f[i][j][k][l] |= (f[i][j-1][k+1][l] && (a[j]==b[k]));

理解了上面的一段后这两行代码也就简单了,有点迷惑的就是为什么不考虑前面的状态图片说明 ,因为要形成的是回文串,所以图片说明图片说明 是一样的,如果可以构成回文串,那么这种情况a提供的字符左右颠倒完全没区别,如果构不成,那就更每影响了。

if(f[i][j][k][l]) ans=max(ans,len1+len2);

如果a、b串提供的字符能组成回文串,那么这就是一个答案,维护最大的答案即可。
Code:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=101;
char a[maxn],b[maxn];
bool f[maxn][maxn][maxn][maxn];
int t,n,m;
int main() {
    scanf("%d",&t);
    while(t--) {
        int ans=0;
        scanf("%s%s",a+1,b+1);
        n=strlen(a+1);
        m=strlen(b+1);
        for(int len1=0;len1<=n;++len1)
        for(int len2=0;len2<=m;++len2)
        for(int i=1;i+len1-1<=n;++i)
        for(int k=1;k+len2-1<=m;++k) {
            int j=i+len1-1,l=k+len2-1;
            if(len1+len2<=1) f[i][j][k][l]=true;
            else {
                f[i][j][k][l]=false;
                if(len1>1) f[i][j][k][l] |= (f[i+1][j-1][k][l]&&a[i]==a[j]);
                if(len1&&len2) f[i][j][k][l] |= (f[i+1][j][k][l-1]&&a[i]==b[l])|(f[i][j-1][k+1][l]&&a[j]==b[k]);
                if(len2>1) f[i][j][k][l] |= (f[i][j][k+1][l-1]&&b[k]==b[l]);
            }
            if(f[i][j][k][l]) ans=max(ans,len1+len2);
        }
        printf("%d\n",ans);
    }
}
每日一题 文章被收录于专栏

牛客每日一题

全部评论

相关推荐

2 收藏 评论
分享
牛客网
牛客企业服务