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 bestprint(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 bestprint(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)。