4

我知道如何使用动态编程来解决给定两个字符串查找最长公共子序列或最长公共子串的问题。但是，我很难找到解决字符串 X 的最长子序列（字符串 Y 的子串）的问题的解决方案。

这是我的蛮力解决方案：

  1. 找到字符串 X 的所有子序列，并按长度 desc 对它们进行排序；
  2. 遍历排序后的子序列，如果当前子序列是 Y 的子串，则返回子序列。

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

是否有更好的方法来做到这一点，可能通过 DP？

编辑：

这是我要解决的示例：

Y: 'BACDBDCD'
X: 'ABCD'

答案是“ACD”，因为“ACD”是X 的最长子序列，也是Y 的子串。

4

2 回答 2

1

这里有两种方法（它们都具有多项式时间复杂度）。
1.生成Y的所有子串（有O(m^2)这样的子串）。对于每个子串，检查它是否是 X 的子序列（可以使用贪心算法在线性时间内完成）。该算法具有O(n * m^2)时间复杂度，这已经不是那么糟糕了。
2.如果不够快，可以O(n * m)使用动态规划来实现时间复杂度。让我们定义=以 X 中的位置和 Yf(i, j)中的位置结束的最长答案。转换如下：i-thj-th

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于0所有有效的i和j。f(n, j)答案是所有有效值中的最大值j。

于 2014-10-09T18:29:30.330 回答
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)
于 2021-05-31T05:49:52.200 回答