一个自己研究出来的字符串匹配算法-k子串算法

Java基础

浏览数:254

2019-5-13

前言

最近工作中需要写一个算法,而写完这个算法我却发现了一个很有意思的事情。需要的这个算法是这样的:对于A,B两个字符串,找出最多K个公共子串,使得这K个子串长度和最大。百度之没有这样的算法,然后就开始想了一些乱七八糟的想法,一一被自己举反例推翻了,直到最后找到了正确算法,我觉得这个思考过程值得记录一下。

思考过程

错误想法1:每次找最长公共子串,找到一个子串后,从A,B两个字符串中删除这个子串,之后在剩下的串中再找最长公共子串,像这样找K次。

举个反例:

A=KABCDELMABCDEFGNFGHIJK

B=KABCDEFGHIJK

K=2

按照这种方式选取结果为:ABCDEFG+HIJK,总长度为7+4=11,但是最优解为:KABCDE+FGHIJK总长度为6+6=12。

错误想法2:求A与B的最长公共子序列,之后从子序列中挑取最长的K段。

举个反例:

A=EFGIJABC

B=ABCEFHIJ

K=1

按照这种方式选取,首先求出最长公共子序列EF-IJ,取出其中最长一段长度为2。而最优解为:ABC,长度为3。

正确解法:动态规划

上面两个看似取巧但是不对的想法被推翻后,也能让我静下心来进行系统性的思考了,正确解法为动态规划。动态规划最重要的事情有三件:找问题的状态,找转移方程边界初始化。找对状态就相当于成功了一半,找到转移方程基本问题就算解了,边界初始化可以忽略不计。找状态除了靠灵感之外,我最喜欢的方法是分解问题,找到问题的最原子的状态,之后搭积木般的组合拼装就OK了。

设dp[i][j][k]表示为以A[i],B[j]为第K个公共子串结尾时,所能得到的最大值。其中A[i]为字符串A第i个字符,B[j]为字符串B的第j个字符。

在考虑A[i]和B[j]时,如果A[i] = B[j],那么A[i],B[j]可以单独组成第K个串,也可以和A[i-1],B[j-1]组合在一起作为第K个串,则转移方程如下:

dp[i][j][k] = dp[i-1][j-1][k] + 1             (与A[i-1],B[j-1]连在一起)

dp[i][j][k] = max(dp[i’][j’][k-1] + 1)      (A[i],B[j]单独成为第K个串)

当单独成串时,需要遍历所有i’,j’,如果我们能在计算dp[i][j][k]的时候顺便记录截止到当前选取k个串时的最大值的话,就可以避免遍历,所以最后的状态以及转移方程如下:

dp[i][j][k] = max(dp[i-1][j-1][k] + 1, maxscore[i-1][j-1][k-1] + 1)

maxscore[i][j][k] = max(maxscore[i-1][j][k],maxscore[i][j-1][k], dp[i][j][k])

现在回头看一下这个算法,当K=1的时候就是最长公共子串问题,当K=min(length(A), length(B))的时候就是最长公共子序列问题,想想还是挺有意思是的。

结语

对于一个棘手的问题,可能一开始想不到正确的算法,我们这时可以尽可能的把能想到的解法全都考虑一遍,该推翻的推翻,该证明的证明,在推翻和证明的过程中更深刻的理解这个问题,最终找到正确的答案。  

作者:haolujun