k-window中相邻元素的最长公共子序列

Question

给定两个字符串和一个 window 大小 k：找到具有约束的最长公共子序列。约束条件是：公共子序列中的相邻元素在一个k-window

内

（理想情况下该约束适用于两个输入字符串。但如果第二个字符串可以满足就可以了）

例如： A = "carpani"

乙="blarpan sharlie paneaui"

和 k = 3

输出：arpan（不是 arpani）。

谁能告诉我如何解决这个问题？如果有人可以 post 伪代码就太好了。

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

k-window中相邻元素的最长公共子序列

Longest Common Subsequence with adjacent elements in k-window

java

algorithm

lcs