递归 - 限制 N 个子串的最长公共子序列

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) returns 8 因为我们有 8 种不同的 U 子串组合，子串数量限制为 m。

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

Answer 1

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

根据你最后的说明，你已经正确地确定我们可以通过解决后缀问题来解决原始问题。我们还知道我们的子问题必须知道我们还剩下多少块要使用。至此，我们可以猜出子问题是什么，并尝试定义一个公式。

我们可以让 f(i,j,k) 是使用 S 的最后 i 个字母匹配 U 的最后 j 个字母的方式的数量恰好 k 个子字符串。什么是边缘情况？如果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 公式的直接翻译运行s 在时间 O(|S| |U|^2 m) 中，而他们的运行s 在 O(|S| |U| m) 中。可以修改我的公式以匹配运行时间，但您需要计算前缀和，以便在预处理和记忆后的 O(1) 时间内可以找到 f(i-l, j-l, k-1) 的每个总和。

Answer 2

要缩短 m，您必须查看 S 中的当前字母和 U。如果两个字母相同你有两个考虑两个（非独家）情况：

您当前正在匹配 S 的子字符串（这意味着，使用你的符号，你已经打开了一个字符串，比如 [aa...) in 在哪种情况下你可以继续匹配
你仍然有严格正数的子字符串需要匹配在这种情况下你可以开始一个新的匹配（无论你现在是什么是否匹配字符串)

为此，您将需要一个额外的递归参数指定您当前是否匹配子字符串。

表明您已找到与您的问题匹配的基本情况是当你到达 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))

递归 - 限制 N 个子串的最长公共子序列

Recursion - Longest Common Subsequence with Restriction on N number of substrings

python

python-3.x

recursion

dynamic-programming