首页 > 试题广场 >

合并回文子串

[编程题]合并回文子串
  • 热度指数:1067 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
输入两个字符串A和B,合并成一个串C,属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度(回文串表示从正反两边看完全一致的字符串,如"aba"和"xyyx")。
需要求出所有可能的C中价值最大的字符串,输出这个最大价值即可

输入描述:
第一行一个整数T(T ≤ 50)。
接下来2T行,每两行两个字符串分别代表A,B(|A|,|B| ≤ 50),A,B的字符集为全体小写字母。


输出描述:
对于每组数据输出一行一个整数表示价值最大的C的价值。
示例1

输入

2
aa
bb
a
aaaabcaa

输出

4
5
不会啊,求大神指点!!!写个思路也行,多谢了
发表于 2017-07-01 16:43:04 回复(0)
递归的理解起来方便一点,时间差一点就超了
#include<iostream>
#include<string>
#include<cstring>
using namespace std;

const int INF=0x3f3f3f3f;

string a,b;
int cache[51][51][51][51];

int dp(int al,int ar,int bl,int br){
  if(al==ar&&bl==br) return 0;
  if((al+1==ar && bl==br)||(al==ar && bl+1==br)) return 1; 

  if(cache[al][ar][bl][br]) return cache[al][ar][bl][br];
  int maxl=-INF;
  if(ar-al>=2 && a[al] == a[ar-1]) maxl= max(maxl,dp(al+1,ar-1,bl,br)+2);
  if(br-bl>=2 && b[bl] == b[br-1]) maxl= max(maxl,dp(al,ar,bl+1,br-1)+2);
  if(br-bl>=1 && ar-al>=1){
    if(a[al] == b[br-1]) maxl= max(maxl,dp(al+1,ar,bl,br-1)+2);
    if(a[ar-1] == b[bl]) maxl= max(maxl,dp(al,ar-1,bl+1,br)+2);
  }
  return cache[al][ar][bl][br] =maxl;
}

int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a>>b;
    
    memset(cache,0,sizeof(cache));
    int res=-INF;
    
    for(int i=0;i<a.size();i++)
      for(int j=i+1;j<=a.size();j++)
        for(int k=0;k<b.size();k++)
          for(int l=k+1;l<=b.size();l++)
            res=max(res,dp(i,j,k,l));

    cout<<res<<endl;
  }
}


发表于 2022-09-03 15:28:45 回复(0)
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf1329103910
typedeflonglongll;
constll mod=1e9+7;
constll N=55;
constdoubleeps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {returnb==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) {returna*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans =1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>=1;}returnans%p;}
ll Inv(ll x){returnqp(x,mod-2,mod);}
ll C(ll n,ll m){if(m>n)return0;ll ans =1;for(inti =1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;returnans%mod;}
intdp[N][N][N][N];
/*
    四个维度分别用i j l k表示
    分别表示 A中i~j 和 B中k~l
*/
chara[N];
charb[N];
intmain()
{
    intt,ans=0,n,m;
    cin>>t;
    while(t--)
    {
      ans=0;
    scanf("%s",a+1);n=strlen(a+1);
    scanf("%s",b+1);m=strlen(b+1);
    for(intd1=0;d1<=n;d1++)
      for(intd2=0;d2<=m;d2++)
        for(inti=1,j=d1;j<=n;i++,j++)
          for(intk=1,l=d2;l<=m;k++,l++)
          {
              if(d1+d2<=1) dp[i][j][k][l]=1;
              else
              {
                 dp[i][j][k][l]=0;
                 if(a[j]==a[i]&&d1>1)
                 {
                   if(dp[i+1][j-1][k][l]) dp[i][j][k][l]=1;
                 }
                 if(a[j]==b[k]&&d1&&d2)
                 {
                   if(dp[i][j-1][k+1][l]) dp[i][j][k][l]=1;
                 }
                 if(b[l]==a[i]&&d1&&d2)
                 {
                   if(dp[i+1][j][k][l-1]) dp[i][j][k][l]=1;
                 }
                 if(b[l]==b[k]&&d2>1)
                 {
                   if(dp[i][j][k+1][l-1]) dp[i][j][k][l]=1;
                 }
              }
              if(dp[i][j][k][l])ans=max(ans,d1+d2);
        }
        cout<<ans<<endl;
    }
    return0;
}
发表于 2022-07-11 14:51:24 回复(0)
python能用4维dp做,但是会超时:
n = int(input())
for _ in range(n):
    a, b = input(), input()
    s, t = len(a), len(b)
    dp = [
        [[[0 for l in range(t + 2)] for k in range(t + 2)] for j in range(s + 2)]
        for i in range(s + 2)
    ]
    ans = 0

    for x in range(s + 1):  # a串中的子串长度
        for y in range(t + 1):  # b串中的子串长度
            #             空串:i=j,x=j-i=0,子串为[i:j] 范围:0<=i=j-x<=s-x
            for i in range(s - x + 1):  # a串右端点
                j = i + x  # a串左端点
                for k in range(t - y + 1):  # b串右端点
                    l = k + y  # b串左端点
                    if x == 0 and y == 0:
                        dp[i][j][k][l] = 1
                    elif x == 0:
                        if y == 1:
                            dp[i][j][k][l] = 1
                        elif b[k] == b[l - 1]:
                            dp[i][j][k][l] = dp[i][j][k + 1][l - 1]
                    elif y == 0:
                        if x == 1:
                            dp[i][j][k][l] = 1
                        elif a[i] == a[j - 1]:
                            dp[i][j][k][l] = dp[i + 1][j - 1][k][l]

                    elif (i < s and k < t) and (
                        (a[i] == a[j - 1] and x > 1 and dp[i + 1][j - 1][k][l])
                       &nbs***bsp;(b[k] == b[l - 1] and y > 1 and dp[i][j][k + 1][l - 1])
                       &nbs***bsp;(l > 0 and a[i] == b[l - 1] and dp[i + 1][j][k][l - 1])
                       &nbs***bsp;(j > 0 and a[j - 1] == b[k] and dp[i][j - 1][k + 1][l])
                    ):
                        dp[i][j][k][l] = 1
                        ans = max(ans, x + y)
    print(ans)


发表于 2022-04-26 21:06:16 回复(0)

热门推荐

通过挑战的用户

查看代码