k窗口中相邻元素的最长公共子序列

Question

给定两个字符串和一个窗口大小 k：找到具有约束的最长公共子序列。约束是：公共子序列中的相邻元素在一个k窗口内（理想情况下，该约束适用于两个输入字符串。但如果可以满足第二个字符串就可以了）例如：A = "carpani"B = "blarpan sharlie paneaui"k = 3输出：arpan（不是 arpani）。有人可以告诉我如何解决这个问题吗？如果有人可以发布伪代码，那就太好了。

Answer 1

这是一个动态规划问题。它们可以通过两种基本方式解决。一种是写一个递归函数，然后memoize。另一种是自底向上构建数据结构。

自上而下的方法通常更容易编写。自下而上的方法通常更有效。这就是为什么两者都要学习的原因。

我将在 Python 中演示自上而下的方法。

考虑以下功能：

def best_k_match_ending_at(string1, string2, k, i, j):

    if string1[i] != string2[j]:

        return (0, None, None)

    else:

        best = (0, None, None)

        for i_old in range(max(i-k, 0), i):

            for j_old in range(max(j-k, 0), j):

                this = best_k_match_ending_at(string1, string2, k, i_old, j_old)

                best = max(best, this)

        return (best[0] + 1, (i, best[1]), (j, best[2]))

def best_k_match(string1, string2, k):

    best = (0, None, None)

    for i in range(len(string1)):

        for j in range(len(string2)):

            best = max(best, best_k_match_ending_at(string1, string2, k, i, j))

    return best

# prints (5, (5, (4, (3, (2, (1, None))))), (6, (5, (4, (3, (2, None)))))

print(best_k_match('carpani', 'blarpan sharlie paneaui', 3))

这是非常低效的。但正确。现在记忆它之前的一步。我喜欢重构以将辅助函数移动到主函数中。逻辑是一样的，但是当我记忆时，它会告诉我何时处理完数据。

def best_k_match(string1, string2, k):

    def best_ending_at(i, j):

        if string1[i] != string2[j]:

            return (0, None, None)

        else:

            best = (0, None, None)

            for i_old in range(max(i-k, 0), i):

                for j_old in range(max(j-k, 0), j):

                    this = best_ending_at(i_old, j_old)

                    best = max(best, this)

            return (best[0] + 1, (i, best[1]), (j, best[2]))

    best = (0, None, None)

    for i in range(len(string1)):

        for j in range(len(string2)):

            best = max(best, best_ending_at(i, j))

    return best

print(best_k_match('carpani', 'blarpan sharlie paneaui', 3))

现在我记住了

def best_k_match(string1, string2, k):

    memoized = {}

    def best_ending_at(i, j):

        if string1[i] != string2[j]:

            return (0, None, None)

        elif (i, j) not in memoized:

            best = (0, None, None)

            for i_old in range(max(i-k, 0), i):

                for j_old in range(max(j-k, 0), j):

                    this = best_ending_at(i_old, j_old)

                    best = max(best, this)

            memoized[(i, j)] = (best[0] + 1, (i, best[1]), (j, best[2]))

        return memoized[(i, j)]

    best = (0, None, None)

    for i in range(len(string1)):

        for j in range(len(string2)):

            best = max(best, best_ending_at(i, j))

    return best

print(best_k_match('carpani', 'blarpan sharlie paneaui', 3))

现在这很有效，但您可能不太喜欢输出。因为它是一个倒序的链表。这是一个更好的输出。

def best_k_match(string1, string2, k):

    memoized = {}

    def best_ending_at(i, j):

        if string1[i] != string2[j]:

            return (0, None, None)

        elif (i, j) not in memoized:

            best = (0, None, None)

            for i_old in range(max(i-k, 0), i):

                for j_old in range(max(j-k, 0), j):

                    this = best_ending_at(i_old, j_old)

                    best = max(best, this)

            memoized[(i, j)] = (best[0] + 1, (i, best[1]), (j, best[2]))

        return memoized[(i, j)]

    best = (0, None, None)

    for i in range(len(string1)):

        for j in range(len(string2)):

            best = max(best, best_ending_at(i, j))

    # Turn linked lists to something nicer.

    best_seq_rev = []

    best_match_rev = []

    best_link_1 = best[1]

    best_link_2 = best[2]

    while best_link_1 is not None:

        best_seq_rev.append(string1[best_link_1[0]])

        best_match_rev.append((best_link_1[0], best_link_2[0]))

        best_link_1 = best_link_1[1]

        best_link_2 = best_link_2[1]

    best_seq = "".join(reversed(best_seq_rev))

    best_match = list(reversed(best_match_rev))

    return (best[0], best_seq, best_match)

# prints (5, 'arpan', [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)])

print(best_k_match('carpani', 'blarpan sharlie paneaui', 3))

如果字符串的长度为n和m，则为O(n*m*k^2)。