首页 > 试题广场 >

合并回文子串

[编程题]合并回文子串

热度指数：1068 时间限制：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

算法知识视频讲解

Python3

朱越峰

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)