找出字符串X的最长子序列，该子序列是字符串Y的子串

Question

找出字符串X的最长子序列，该子序列是字符串Y的子串

pythonstringalgorithmsubstringsubsequence

4

我知道如何使用动态规划来解决找到两个字符串之间的最长公共子序列或最长公共子串的问题。然而，我很难找到一种解决方法来找到字符串X的最长子序列，该子序列是字符串Y的子串。

这是我暴力解决方案：

查找字符串X所有子序列，并按长度降序排序；
遍历排序后的子序列，如果当前子序列是Y的子串，则返回该子序列。

它可以工作，但运行时间可能很糟糕。假设X中的所有字符都是唯一的，则有2^m个子序列，其中m是X的长度。我认为检查一个字符串是否是Y的子串需要O(n)的时间，其中n是Y的长度。因此，总运行时间为O(n*2^m)。

有更好的方法来解决这个问题吗？可能通过DP实现？

编辑：

这里是我想要解决的问题的示例：

Y: 'BACDBDCD'
X: 'ABCD'

答案是 'ACD'，因为'ACD'是X的最长子序列，也是Y的子字符串。

- Skiptomylu

1

当你知道动态规划算法具有最佳渐进复杂度时，为什么不想使用它呢？ - Carmine Ingaldi

2

为什么会有踩票？他说他想使用 DP。 - Juan Lopes

你看过http://en.wikipedia.org/wiki/Longest_common_subsequence_problem吗？它非常清楚地说明动态规划是正确的解决方案，可以在多项式时间内解决问题。你的第一句话说你已经知道如何做了，那么问题出在哪里呢？（我没有投反对票）[编辑也许我误读了你的开头评论...你说你知道如何找到最常见的而不是最长的] - Joran Beasley

@sscnapoli1926 DP是我正在寻找的解决方案，但我不知道该如何实现。也许我的措辞有些令人困惑... - Skiptomylu

@JoranBeasley 我已经阅读了这篇文章，但我认为我的问题不同。请看我的编辑。 - Skiptomylu

哦，我明白了...那有点复杂...对我来说，子序列和子字符串是相当可互换的...抱歉我误解了。 - Joran Beasley

3个回答

0

在Python中，你不需要使用动态规划来解决它。利用修改运行时的for循环语法的灵活性来实现它：

current_len=0
subseq_len = 0
subseq_data=''
array1 = "ABCBDAB"
array2 = "BDCABA"
#array1="MICHAELANGELO"
#array2="HELLO"
m=len(array1)
n=len(array2)
#loop over first string array1 
#and increment index k to form new substrings of len-1
for k in range(0,m):
    start=0
    current_len = 0
    cur_seq =''
    #substring starting at k to m of array1
    for i in range(k,m):
        for j in range(start,n):
            if array1[i]==array2[j]:
                #increment length of matched subsequence
                current_len +=1
                #move forward index to point to remaining sub string array2
                start=j+1
                cur_seq = cur_seq+array1[i]
                break
        #print(k)
        #print(":"+cur_seq)
    #Check if current iteration for k produced longer match
    if subseq_len < current_len:
        subseq_len = current_len
        subseq_data = cur_seq
    enter code here

print(subseq_data)
print(subseq_len)

- ALOK KUMAR SRIVASTAVA

0

这里是 GFG 上其解决方案的链接：查找一个字符串的最长子序列长度，该子序列是另一个字符串的子串

- NOOB CODER

虽然这个链接可能回答了问题，但最好在此处包含答案的基本部分并提供参考链接。如果链接页面更改，仅有链接的答案可能会失效。-【来自审查】 - Muhammad Mohsin Khan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kraskevich · Accepted Answer

这里有两种做法（两种都具有多项式时间复杂度）。
1. 生成Y的所有子串（共O(m^2)个子串）。对于每个子串，检查它是否是X的子序列（可以使用贪心算法在线性时间内完成）。此算法的时间复杂度为O(n * m^2)，已经不错了。
2. 如果速度还不够快，可以使用动态规划实现O(n * m)时间复杂度。让我们定义f(i, j)为以X中第i个位置和Y中第j个位置结尾的最长答案。转移如下：

f(i + 1, j) = max(f(i + 1, j), f(i, j)) //skip this character in X
if X[i] == Y[j] //add this character to current answer
    f(i + 1, j + 1) = max(f(i + 1, j + 1), f(i, j) + 1)

f 的初始值对于所有有效的 i 和 j 均为 0。答案是所有有效的 j 中 f(n, j) 的最大值。