Longest Common Subsequence

Published: by Creative Commons Licence

  • Tags:

简述

LCS(Longest common sequence)问题指的是提供两个长度为N的串n和长度为M的串m,求两个串最长的公共子串。其中a是b的子串当且仅当b删除若干个字符后可以得到a,比如"b"是"abc"的子串。

这个问题相当有趣,并且也非常实用。LCS还有一个镜像问题,以最少的修改次数将字符串n转换为m,修改仅允许以下三种操作:

  1. 从n中删除一个字符
  2. 向n中插入一个字符

LCS问题的经典应用场景有diff和增量计算。

解法

下面讨论两种解决LCS的算法。

动态规划

LCS的典型解法就是动态规划。首先我们定义:dp[i][j]=n[0..i]与m[0..j]的最长子串的长度。

之后我们发现对于n[0..i]与m[0..j]的最长子串的计算,仅会发生下面三种情况:

  • n[i]与m[j]匹配,则此时dp[i][j]=dp[i-1][j-1]+1
  • n[i]与m[j]不匹配,此时若二者的最长子串不包含n[i],则dp[i][j]=dp[i-1][j]
  • n[i]与m[j]不匹配,此时若二者的最长子串不包含m[j],则dp[i][j]=dp[i][j-1]
int lazyDp(int i, int j)
{
    if(i < 0 || j < 0)
    {
        return 0;
    }
    if(dp[i][j] == -1)
    {
        dp[i][j] = n[i] == m[j] ? lazyDp(i - 1, j - 1) + 1 : max(lazyDp(i - 1, j), lazyDp(i, j - 1));
    }
    return dp[i][j];
}

动态规划的时间复杂度和空间复杂度均为O(NM)。

由于动态规划中dp代表的是一个二维矩阵,且每个单元格仅依赖于左边,上边,左上边的三个元素的值,那么我们可以利用Method of four Russians中提到的算法将其优化到O(NM/log2(N))。

贪心算法

在Eugene W.Myers的论文中提到了一个贪心算法,其时间复杂度为O(ND),其中D为实际最少操作次数。譬如我们仅对n做了1一次操作得到了m,那么D就是1,此时算法是线性的。

下面来了解一下这个算法。

首先我们可以将二维DP转换为图论问题。首先我们建立有向图G,我们可以将其视作一张二维图,G[y][x]表示二维图的第y行第x列对应的顶点,我们对于每一个i,j建立如下边:

  • 若n[i]与m[j]相同,则建立一条长度为0的边(G[i][j],G[i+1][j+1])。对于若干前后相连的该类边构造的路径,我们称其为蛇。
  • 建立长度为1的边(G[i][j],G[i+1][j])
  • 建立长度为1的边(G[i][j],G[i][j])

而寻找lcs等价于寻找从G[1][1]到G[N][M]的最短路。

接下来我们将图切分为多条轨迹,切分规则为:对于顶点G[i][j],其属于轨迹(i-j)。很显然轨迹集合为{-M,-M+2,…,N},共N+M+1条轨迹。

如果G[i][j]距离G[1][1]的最短距离为d,则称G[i][j]落在i-j轨迹上的d片段上,记作(i-j,d)。

现在我们给出下面两个命题:

命题1:
(1)偶数号轨迹仅有偶数片段。
(2)奇数号轨迹仅有奇数片段。

证明:当d为0时,我们可以确定其仅落在轨迹0上。若d<k时命题始终成立,当d=k时,其必然通过一个k-1片段上移动1距离到达,当然其中可能涉及到沿着蛇移动的情况,但是蛇不改变轨迹。下面不失一般性假设k为偶数,则k-1片段仅落在奇数号轨迹上,沿着x增大或y增大的边移动距离1,则轨迹号降低或增大1,故k落在偶数号轨迹上。
命题2:对于轨迹t,其仅有片段{t,t+2,t+4,...}

证明:要到达轨迹t,令y增大的移动的次数必须比令x增大的移动的次数多t。

对于指定的t,d,片段(t,d)实际上可能包含多个顶点,我们定义L(t,d)表示片段(t,d)包含的所有顶点的最大y值,由于L(t,d)一旦确定,就唯一指定了一个顶点,因此我们将其无差别视作一个顶点处理。

命题3:对于顶点L(t,d),其必然是由L(t-1,d-1)向下移动一步或L(t+1,d-1)移动向右移动一步后,并沿着蛇移动到末尾得到的

证明:首先我们可以确定如果从某点x移动距离1后并沿着蛇到末尾抵达轨迹t上顶点y,那么x必定落在轨迹t-1,t,t+1之中。之后如果y距离起点d的距离,且x处于起点到y的最短路径上,那么起点到x的最短距离一定是d-1。我们到此已经确认了x处于(t-1,d-1)或(t+1,d-1)上,接下来只需要证明当y为L(t,d)时,由L(t-1,d-1)或L(t+1,d-1)移动一步后沿着蛇可以抵达y。不妨假设x处于(t-1,d-1)上,且不是L(t-1,d-1)。那么我们同时由(t-1,d-1)上任意点p和L(t-1,d-1)向下移动一部到达轨迹t上的顶点p',L',很显然L'的深度要大于p',因此从p'沿着蛇移动抵达的目的地深度一定不会大于沿着L'移动的最终目的地。

因此我们得到了最后的算法流程,对于每个d,计算每个轨迹t的L(t,d)。而一旦L(N-M,d)为N,那么结果就得到。

下面给出代码:

lcs(n, m)
    N = |n|
    M = |m|
    L = [-M,N] filled with -1
    for(d = 0; ; d += 1)
        for(t = -d; t <= d; t += 2)
            L[t] = max(L[t - 1] + 1, L[t + 1])
            //L[t] - x = t -> x = L[t] - t
            while(L[t] < N && L[t] - t < M && n[L[t]] == m[L[t] - t])
                L[t] += 1
    		if(L[t] == N && t == N - M)
                return d

由于在d为D时最外层循环就会结束,而第二层循环每次也仅执行D次,故两个循环内除while外总的时间复杂度为O(D^2)。while循环每次执行都会将L[t]增大1,考虑到我们仅操作L[-D],L[-D+1],…,L[D],而每个值最大为N,故while的总时间复杂度至多为O(ND)。因此实际时间复杂度为O(ND)。而空间复杂度,假如仅需寻找lcs的最少操作次数,则为O(N+M),如果还需要记录每次实际操作,则需要O((N+M)D)。