子串个数受限的递归最长公共子序列

Question

我真的被一个问题困住了，给我一个字符串输入S，另一个字符串输入U代表整个子字符串和一个非负整数m。方法是lcs（S，U，m）

例如：设S=“aabacaab”，U=“aab”，m=2。然后我们有以下子串组合：

[a][ab]acaab

[a]abaca[ab]

a[a]baca[ab]

aab[a]ca[ab]

aabac[a][ab]

[aa][b]acaab

[aa]bacaa[b]

aabac[aa][b]

因此lcs(S, U, m)返回8，因为我们有8个不同的U子串组合，并且子串的m个数受到限制

我最初的想法是将S的第一个字符与U的第一个字符进行比较，并通过缩短S和U来向下递归。但是，由于m，我无法确定如何减少m，因为缩短的S和U没有任何前一个状态的引用

Answer 1

在处理字符串上的动态编程时，“我的子问题应该是什么”的答案通常是前缀、后缀或子字符串

从你最后的笔记中，你已经正确地认识到我们可以通过解决后缀问题来解决原来的问题。我们还知道，我们的子问题必须知道剩下要使用的工件数量。此时，我们可以猜测子问题是什么，并尝试定义一个公式

我们可以让f(i,j,k)成为使用S的最后i个字母精确地k子字符串来匹配U的最后j个字母的方法数。什么是边缘案例？如果j和k都是0，我们就没什么关系了；有一种方法可以什么都不做。如果i<j我们无法匹配j个字母，如果j<k我们无法将j个字母分割成足够的片段

最后，您必须定义主递归。首先，我们可以跳过S的这个字母，它将f(i-1,j,k)作为求和。现在，让Match-Length(i,j)为S[-i:]开头与U[-j:]匹配的连续位置数。我们需要添加所有可能的匹配项：对于每个长度l，1 <= l <= Match-Length(i,j)，我们必须添加f(i-l, j-l, k-1)。这包括所有情况

编辑：用户qouify发布了一个更好的解决方案。此DP公式的直接翻译在时间O(|S| |U|^2 m)中运行，而他们的直接翻译在时间O(|S| |U| m)中运行。可以修改我的公式以匹配该运行时，但您需要计算前缀和，以便在预处理和记忆后的f(i-l, j-l, k-1)时间内可以找到O(1)的每个和

Answer 2

要缩短m，您必须查看S中的当前字母 和U。如果两个字母相同，则有两个（非 （排他性）情况：

• 您当前正在匹配S的子字符串（这意味着使用 您已经打开了一个字符串，如[aa...中的符号 哪种情况下可以继续匹配

• 您仍然有严格正数量的子字符串要匹配 在哪种情况下，您可以开始新的匹配（无论您当前是什么） 是否匹配字符串）

为此，您将需要一个用于递归的附加参数 它指定当前是否匹配子字符串

指示已找到与问题匹配的基本情况 是当您到达U的末尾并且m等于0时

以下是实现此解决方案的代码（请注意，该函数处理字母列表而不是字符串）：

#!/usr/bin/env python3

import functools

def lcs(s, u, m) -> int:

    # recursive function
    #   i: index in list s
    #   j: index in list j
    #   m: number of sub-strings to find
    #   match: are we currently matching a sub-string or not?
    @functools.lru_cache(maxsize=10000)  #  cache the result of our function
    def loop(i, j, m, match) -> int:
        # base cases
        if j >= len(u):  # end of u reached => no more letter to look for
            if m == 0: # check if have found our m sub-strings
                return 1
            return 0
        if i >= len(s):  # end of s reached and still letter to look for 
            return 0

        result = loop(i + 1, j, m, False)  # skip the current letter

        # letter in s and u are the same (we will move both i and j)
        if s[i] == u[j]:
            if match:  # we are currently matching a sub-string => continue
                result += loop(i + 1, j + 1, m, True)
            if m > 0:  # we can start a new sub-string
                result += loop(i + 1, j + 1, m - 1, True)
        return result

    return loop(0, 0, m, False)

print(lcs(list("aabacaab"), list("aab"), 2))