hiho一下第60周《String Matching Content Length》题目分析

12
11

题意分析

给定只包含字母的两个字符串A,B,求A,B两个字符串的最长公共子序列,要求构成子序列的子串长度都必须大于等于3。

比如"abcdefghijklmn""ababceghjklmn",其最长满足题意要求的子序列为"abcjklmn",其由公共子串"abc""jklmn"组成。

这里我们要注意子串子序列的区别:

  • 子串:连续的元素
  • 子序列:不连续的元素

比如"abcdefghijklmn""ababceghjklmn"的最长公共子串就只是"jklmn"了。

算法分析

首先我们来复习一道经典的题目:

给定只包含字母的两个字符串A,B,求A,B两个字符串的最长公共子序列

比如"abcde""abdfg"的最长公共子序列"abd"

对于最长公共子序列,我们知道解法为

dp[0][0..j] = 0    // 边界
dp[0..i][0] = 0    // 边界
For i = 1 .. n
    For j = 1 .. m
        If a[i] == b[j] Then
            dp[i][j] = dp[i - 1][j - 1] + 1
        Else
            dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1])
        End If
    End For
End For

而这一道题目是在最长公共子序列上加入了一个条件:构成最长公共子序列的每一个子串长度必须大于等于3.

一个简单的想法:我们求出最长公共子序列,然后将其中长度小于3的部分去掉。

显然,这是不对的。

举个例子:"aaabaa""acaaaca"的最长子序列为"aaaaa"。其对应关系为:

a aaba a
acaa aca

因为在"acaaaca"中第一个字母a长度为1,所以我们需要去掉它,对应的我们也去掉了"aaabaa"中第一个字母a。

.  aaba a
. caa aca

此时构成"aaabaa""acaaaca"公共子序列的3个子串为"aa","a""a",长度都小于了3,所以全部删去,则得到了新的公共子序列长度为0。

这显然不正确,因为实际有符合题意要求的公共子序列:

   aaa baa
ac aaa ca

其中包含有长度为3的公共子序列。

对最大公共子序列的结果进行再次处理这个方法不可行,那么我们只能从计算公共子序列的算法着手。

首先我想我们可以做一个预处理,用f[i][j]表示以a的第i个字母作为结尾的前缀和*以b的第j个字母作为结尾的前缀*的公共后缀的长度。这样看上去似乎很绕,不如举个例子:

a="abcd"和b="acbc"f[3][4]的就表示a[1..3]和b[1..4]的公共后缀的长度,其中a[1..3]="abc",b[1..4]="acbc",其公共后缀为"bc",所以f[3][4]=2.

预处理的伪代码为:

For i = 1 .. n
    For j = 1 .. m
        If a[i] == b[j] Then
            f[i][j] = f[i - 1][j - 1] + 1
        Else
            f[i][j] = 0
        End If
    End For
End For

有了这个预处理的数组,我们可以在原来最大公共子序列上做这样一个改进:

dp[0][0..j] = 0    // 边界
dp[0..i][0] = 0    // 边界
For i = 1 .. n
    For j = 1 .. m
        If f[i][j] >= 3 Then    // 改进
            dp[i][j] = dp[i - f[i][j]][j - f[i][j]] + f[i][j]
        Else
            dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1])
        End If
    End For
End For

这个改进的意义为:当我们出现一个长度大于3的子串时,我们就直接将这个子串合并入我们的子序列。

加入这个改进后,我们通过了样例的数据,这样看上去似乎就应该没什么问题了。

然而事实并不是这样,在这道题目中还隐藏着陷阱

比如"abcdef""abcxcdef"

根据我们算法,上面这个例子算出的结果为4,然而其实际的结果应该为6,即"abc""def"两个公共子串构成的子序列。

那么出错的原因在哪?就在字符串"cdef"上。

我们计算结果出4是因为将"cdef"看做了一个整体,而将"abcdef"分割成了"ab""cdef"

在DP的过程中f[6][7] = 4,我们使用了dp[6][7] = dp[2][3] + 4,而dp[2][3] = 0,所以dp[6][7] = 4。

ab  cdef
abcxcdef

而实际上的最有解是将f[6][7]看作3,dp[6][7] = dp[3][4] + 3,其中dp[3][4] = 3,得到了dp[6][7] = 6。

abc  def
abcxcdef

也就是说,如果我们将f[i][j]>3的子串进行分割,有可能得到更优的情况。因此我们需要进一步的改进:

dp[0][0..j] = 0    // 边界
dp[0..i][0] = 0    // 边界
For i = 1 .. n
    For j = 1 .. m
        dp[i][j] = 0
        If f[i][j] >= 3 Then    // 改进
            For k = 3 .. f[i][j]    // 枚举分割长度
                dp[i][j] = Max(dp[i][j], dp[i - k][j - k] + k)
            End For
        Else
            dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1])
        End If
    End For
End For

但是这样的改进使得整个算法的时间复杂度变为了O(n^3),当n=2100时,有可能会超时。

让我们考虑一下如何进一步改进这个算法。以上算法复杂度高的地方在于对于每一个(i, j),我们为了计算dp[i][j]都需要枚举分割长度k:

For k = 3 .. f[i][j]    // 枚举分割长度
    dp[i][j] = Max(dp[i][j], dp[i - k][j - k] + k)
End For

这一步实际上我们计算了max{dp[i-k][j-k]+k}, k=3..f[i][j]。我们不妨把它记作dp1[i][j],即:

dp1[i][j] = max{dp[i-k][j-k]+k} = max{dp[i-3][j-3]+3, dp[i-4][j-4]+4, dp[i-5][j-5]+5, ... }

同时

dp1[i-1][j-1] = max{dp[i-1-3][j-1-3]+3, dp[i-1-4][j-1-4] + 4, dp[i-1-5][j-1-5]+5 ... }
    = max{dp[i-4][j-4]+3, dp[i-5][j-5]+4, dp[i-6][j-6]+5, ... }

我们可以发现,dp1[i][j]的展开式中除了dp[i-3][j-3]+3这一项,是与dp1[i-1][j-1]中的每一项一一对应的,并且刚好大1。所以实际上dp[i-1][j-1]计算时枚举过分割长度,我们并不需要再次计算:

dp1[i][j] = max{dp1[i-1][j-1] + 1, dp[i-3][j-3]+3}

最后得到我们新的伪代码如下,其中dp[i][j][0]对应上文分析中的dp[i][j], dp[i][j][1]对应dp1[i][j]:

dp[0][0..j][0..1] = 0    // 边界
dp[0..i][0][0..1] = 0    // 边界
For i = 1 .. n
    For j = 1 .. m
        dp[i][j][1] = 0
        If f[i][j] >= 3 Then    // 改进
            dp[i][j][1] = Max(dp[i][j][1], dp[i - 3][j - 3][0] + 3)     // 以长度3为分割
            If (f[i][j] > 3) Then
                //按照dp[i-1][j-1][1]的分割方式分割,即直接将(i,j)接在(i-1,j-1)后面
                dp[i][j][1] = Max(dp[i][j][1], dp[i - 1][j - 1][1] + 1)
            End If
        End If
        dp[i][j][0] = Max(dp[i-1][j][0], dp[i][j-1][0], dp[i][j][1])
    End For
End For

至此我这道题目也算是完整的解出了。

结果分析

这个题目是在经典的动态规划题目《最长公共子序列》上做了一点修改。虽然只增加了一个条件,不过难度增大很多。能想出一个复杂度是O(n^2)的正确算法不是很容易,需要仔细分析清楚各种情况。一不小心就会掉进各种陷阱里。

很多选手都能够想到经典最长子序列的改进算法而获得80分。

剩下的测试点则对应了算法分析中提到的陷阱,所以能否找出这种特殊的例子也是解决这道题的关键。

不过微软的出题人似乎没有想太为难大家,数据并不是很强。在实际的比赛中,O(n^3)的算法也能拿到满分,最终该题目的通过率为9%。

很多O(N^2)的程序不能通过"babad""babacabad"这组数据。

7 answer(s)

0

dp[i][j][0] = Max(dp[i-1][j][0], dp[i][j-1][0], dp[i][j][1]) 没有必要,dp[i][j][0] 一定等于dp[i][j][1],整个DP数组可就只需要两维就够了。

  • dp[i][j][0]并不一定等于dp[i][j][1]。我看了你的程序,虽然最后结果对了,但是中间很多dp[i][j]的值是不正确的。也许你的dp[i][j]定义有些不同?

  • 没有,其实DP[I][J][0]与DP[I][J][1]的定义是重合的

  • 你定义DP[I][J][0]=MAX(DP[I-K][J-K][1]+K),K∈[3..f[i][j]],实际上DP[i][j][1]=MAX(DP[I][J][0]+1,DP[I-3][J-3][1]+3)=MAX(DP[I-K][J-K][1]+K),这两个绕了一圈又重合了

  • DP[I][J][0]并不是MAX(DP[I-K][J-K][1]+K),K∈[3..f[i][j]]。你可以试一下"baba"和"babacaba"这组数据,我的dp[4][8][0]是4,dp[4][8][1]是3。而你的程序dp[4][8]=3,我觉得如果你的dp定义和我一样的话,dp[4][8]的值是错的。

  • 我的代码有一个地方有漏洞 if(f[i][j]==3)dp[i][j]=dp[i-3][j-3]+3; 这个地方出现了错误,应该是 if(f[i][j]==3)dp[i][j]=max(max(dp[i-1][j],dp[i][j-1]),dp[i-3][j-3]+3); 我一开始开文章的时候“其中dp[i][j][0]对应上文分析中的dp[i][j], dp[i][j][1]对应dp1[i][j]”这句话漏掉了,不过确实可以转化成二维,辅助数组是可以去掉的。

  • 中间计算的转移值要一直与max(dp[i-1][j],dp[i][j-1])比较忘记了,谢谢哦。

  • 为什么一直要与max(dp[i-1][j],dp[i][j-1])比较呢? 传统的最长公共子序列算法并不需要啊。求大神证明一下

  • 好像dp[i][j][0] 一直是等于dp[i][j][1]的

  • 添加评论
  • reply
6

o(n^3)次方的伪代码有问题,无论是否有f[i][j]>=3都应该更新dp[i][j]即:dp[i][j] = Max(dp[i-1][j],dp[i][j-1]) 伪代码应改为:

dp[0][0..j] = 0    // 边界
dp[0..i][0] = 0    // 边界
For i = 1 .. n
    For j = 1 .. m
        dp[i][j] = 0
        dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1])
        If f[i][j] >= 3 Then    // 改进
            For k = 3 .. f[i][j]    // 枚举分割长度
                dp[i][j] = Max(dp[i][j], dp[i - k][j - k] + k)
            End For
        End If
    End For
End For
  • 谢谢提醒,本来是90,看了您的提醒后就100了,但是我想不出为什么,可以告诉我吗?

  • 比如"12345"和"1234345"这样的数据

  • Thx @Nettle. 这道题的坑还真是多...

  • 多谢指点

  • 添加评论
  • reply
2

辅助数组是不需要的,已经推导出:dp1[i][j] = max{dp1[i-1][j-1] + 1, dp[i-3][j-3]+3}, 可以看出dp1只要枚举两个地方:

  1. (i - f[i][j], j - f[i][j])
  2. (i - 3, j - 3)

所以得出这样性质以后直接用在dp上就好了,dp[i][j] = max(dp[i - 3][j - 3] + 3, dp[i - f[i][j]][j - f[i][j]])。

  • 老兄,你说的很对

  • 腻不是用了么?

  • "abcdefgh" "abcxcdefgh" ans=8 这组数据过不去

  • 我怎么觉得是 dp[I][j] = max(dp[I-3][j-3]+3,dp[I-1][j-1]+1)?

  • 添加评论
  • reply
2

只需考虑max(dp[i-k][j-k]+k,f[i][j]-3<=k<=f[i][j]),因为这样就可以防止dp[i][j]在计算过程中为了贪1到2个字符而拆散了前面三个字符一组

1

感觉被启发了 :)

0

突然发现楼上的楼上算法更好

0

感觉最终的伪代码里,可以在判断完f[i][j]>=3后直接把dp[i][j][1]赋值为dp[i-3][j-3]+3,不用再max了。。。

write answer 切换为英文 切换为中文


转发分享