查找两个字符串之间的共同有序字符

Question

给定两个字符串，找到两个字符串之间从左到右顺序相同的公共字符。实施例1string_1 = 'hcarry'string_2 = 'sallyc'Output - 'ay'实施例2string_1 = 'jenny'string_2 = 'ydjeu'Output - 'je'示例 1 的解释 -string_1和之间的常见字符string_2是 c、a、y。但由于c位于ayin之前string_1  和之后，我们不会考虑输出中的ay字符。两个字符串之间的公共字符的顺序必须保持并且必须相同。string_2c示例 2 的解释 -string_1和之间的公共字符string_2是 j、e、y。但由于y位于jein之前string_2  和之后，我们不会考虑输出中的je字符。两个字符串之间的公共字符的顺序必须保持并且必须相同。string_1y我的做法——查找字符串之间的公共字符，然后将其存储在每个单独字符串的另一个变量中。Example - string_1 = 'hcarry'string_2 = 'sallyc'Common_characters = c,a,ystring_1_com = caystring_2_com = ayc我使用sorted, counter, enumerate函数来进入string_1_com and string_2_com Python。现在找到 之间的最长公共子序列string_1_com and string_2_com 。您将得到输出作为结果。这是蛮力解决方案。对此的最佳解决方案是什么？

Answer 1

在我的书中，这种算法被称为字符串匹配。它的运行时间复杂度为 O( mn )，其中m和n是字长。我想它也可以在完整的单词上运行，最有效的方法取决于预期的常见字母数量以及如何执行排序和过滤。我将针对常见字母字符串进行解释，因为这样更容易。

这个想法是，您查看(m+1) * (n+1)个节点的有向无环图。通过该图的每条路径（从左上到右下）代表了匹配单词的独特方式。我们想要匹配字符串，并-在单词中添加空格 ( )，以便它们与最多的常见字母对齐。例如cay和的最终状态ayc是

cay-

-ayc

每个节点存储其代表的部分匹配的最大匹配数，并且在算法结束时，结束节点将为我们提供最大匹配数。

我们从左上角开始，那里没有任何东西匹配，所以这里有 0 个匹配的字母（得分 0）。

    c a y

  0 . . .

a . . . .

y . . . .

c . . . .

我们将遍历该图，并使用先前节点的数据为每个节点计算匹配字母的最大数量。

节点从左->右、上->下以及对角从左上->右-下连接。

向右移动代表使用 中的一个字母cay并将我们到达的字母与-插入的字母相匹配ayc。

向下移动代表相反的情况（从 消耗ayc并插入-到cay）。

对角线移动表示消耗每个单词中的一个字母并匹配它们。

查看起始节点右侧的第一个节点，它表示匹配

c

-

并且这个节点（显然）只能从起始节点到达。

第一行和第一列中的所有节点都将为 0，因为它们都表示与相同数量的 匹配的一个或多个字母-。

我们得到图表

    c a y

  0 0 0 0

a 0 . . .

y 0 . . .

c 0 . . .

这就是设置，现在有趣的部分开始了。

查看第一个未评估的节点，它表示将子字符串c与匹配a，我们想要决定如何以最多数量的匹配字母到达那里。

替代方案 1：我们可以从左边的节点到达那里。左边的节点代表匹配

-

a

因此，通过选择这条路径到达当前节点，我们到达

-c

a-

匹配c给-我们没有正确的匹配，因此该路径的分数是 0（取自最后一个节点）加上 0（c/-刚刚进行的匹配的分数）。所以这条路径的 0 + 0 = 0。

方案2：我们可以从上面到达这个节点，这条路径代表从

c   ->    c-

-         -a

这也给我们 0 分。此项得分为 0。

替代方案 3：我们可以从左上角到达该节点。这是从起始节点（什么都没有）转变为消耗每个字母中的一个字符。那就是匹配

c

a

由于c和a是不同的字母，因此这条路径也得到 0 + 0 = 0。

    c a y

  0 0 0 0

a 0 0 . .

y 0 . . .

c 0 . . .

但对于下一个节点来说，它看起来更好。我们仍然可以考虑三种选择。替代方案 1 和 2 总是给我们 0 额外分，因为它们总是表示将字母与 匹配-，因此这些路径将为我们提供 0 分。让我们继续讨论替代方案 3。

对于我们当前的节点，对角移动意味着从

c   ->   ca

-        -a

这是一场比赛！

这意味着有一条通往该节点的路径为我们提供了 1 分。我们扔掉 0 并保留 1。

    c a y

  0 0 0 0

a 0 0 1 .

y 0 . . .

c 0 . . .

对于这一行的最后一个节点，我们查看了三个替代方案，并意识到我们不会获得任何新点（新匹配），但我们可以使用之前的 1 点路径到达该节点：

ca   ->   cay

-a        -a-

所以这个节点的score也是1。

对所有节点执行此操作，我们得到以下完整图表

    c a y

  0 0 0 0

a 0 0 1 1

y 0 0 1 2

c 0 1 1 2

分数唯一增加的地方来自于

c   ->   ca   |   ca   ->   cay   |   -   ->   -c

-        -a   |   -a        -ay   |   y        yc

所以结束节点告诉我们最大匹配是 2 个字母。由于在您的情况下您希望知道得分为 2 的最长路径，因此您还需要跟踪每个节点所采用的路径。

该图很容易实现为矩阵（或数组的数组）。

我建议您作为元素使用tuple带有一个score元素和一个path元素的 a ，并且在路径元素中您只存储对齐字母，那么最终矩阵的元素将是

    c      a        y

  0 0      0        0

a 0 0      (1, a)   (1, a)

y 0 0      (1, a)   (2, ay)

c 0 (1, c) (1, a/c) (2, ay)

在我注意到的一处a/c，这是因为 stringca和ayc具有两个不同的最大长度子序列。您需要决定在这些情况下该怎么做，要么只选择其中一个，要么保留两者。

编辑：

这是此解决方案的实现。

def longest_common(string_1, string_2):

    len_1 = len(string_1)

    len_2 = len(string_2)

    

    m = [[(0,"") for _ in range(len_1 + 1)] for _ in range(len_2 + 1)] # intitate matrix

    

    for row in range(1, len_2+1):

        for col in range(1, len_1+1):

            diag = 0

            match = ""

            if string_1[col-1] == string_2[row-1]: # score increase with one if letters match in diagonal move

                diag = 1

                match = string_1[col - 1]

            # find best alternative

            if m[row][col-1][0] >= m[row-1][col][0] and m[row][col-1][0] >= m[row-1][col-1][0]+diag:

                m[row][col] = m[row][col-1] # path from left is best

            elif m[row-1][col][0] >= m[row-1][col-1][0]+diag:

                m[row][col] = m[row-1][col] # path from above is best

            else:

                m[row][col] = (m[row-1][col-1][0]+diag, m[row-1][col-1][1]+match) # path diagonally is best

    return m[len_2][len_1][1]

>>> print(longest_common("hcarry", "sallyc"))

ay

>>> print(longest_common("cay", "ayc"))

ay

>>> m

[[(0, ''), (0, ''), (0, ''), (0, '')],

 [(0, ''), (0, ''), (1, 'a'), (1, 'a')],

 [(0, ''), (0, ''), (1, 'a'), (2, 'ay')],

 [(0, ''), (1, 'c'), (1, 'c'), (2, 'ay')]]

Answer 2

这是该问题的一个简单的、基于动态规划的实现：

def lcs(X, Y): 

    m, n = len(X), len(Y)

    L = [[0 for x in xrange(n+1)] for x in xrange(m+1)] 

  

    # using a 2D Matrix for dynamic programming

    # L[i][j] stores length of longest common string for X[0:i] and Y[0:j]

    for i in range(m+1): 

        for j in range(n+1): 

            if i == 0 or j == 0: 

                L[i][j] = 0

            elif X[i-1] == Y[j-1]: 

                L[i][j] = L[i-1][j-1] + 1

            else: 

                L[i][j] = max(L[i-1][j], L[i][j-1]) 

  

    # Following code is used to find the common string 

    index = L[m][n] 

  

    # Create a character array to store the lcs string 

    lcs = [""] * (index+1) 

    lcs[index] = "" 

  

    # Start from the right-most-bottom-most corner and 

    # one by one store characters in lcs[] 

    i = m 

    j = n 

    while i > 0 and j > 0: 

  

        # If current character in X[] and Y are same, then 

        # current character is part of LCS 

        if X[i-1] == Y[j-1]: 

            lcs[index-1] = X[i-1] 

            i-=1

            j-=1

            index-=1

  

        # If not same, then find the larger of two and 

        # go in the direction of larger value 

        elif L[i-1][j] > L[i][j-1]: 

            i-=1

        else: 

            j-=1

  

    print ("".join(lcs))

Answer 3

更简单的解决方案-----谢谢！

def f(s, s1):

 cc = list(set(s) & set(s1))

 ns = ''.join([S for S in s if S in cc])

 ns1 = ''.join([S for S in s1 if S in cc])

 found = []

 b = ns[0]

 for e in ns[1:]:

    cs = b+e

    if cs in ns1:

        found.append(cs)

    b = e

 return found

Answer 4

但是..您已经知道术语“最长公共子序列”并且可以找到大量动态规划算法的描述。

伪代码

function LCSLength(X[1..m], Y[1..n])

    C = array(0..m, 0..n)

    for i := 0..m

        C[i,0] = 0

    for j := 0..n

        C[0,j] = 0

    for i := 1..m

        for j := 1..n

            if X[i] = Y[j] //i-1 and j-1 if reading X & Y from zero

                C[i,j] := C[i-1,j-1] + 1

            else

                C[i,j] := max(C[i,j-1], C[i-1,j])

    return C[m,n]

function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)

    if i = 0 or j = 0

        return ""

    if  X[i] = Y[j]

        return backtrack(C, X, Y, i-1, j-1) + X[i]

    if C[i,j-1] > C[i-1,j]

        return backtrack(C, X, Y, i, j-1)

    return backtrack(C, X, Y, i-1, j)