最长公共子串算法(Longest Common Substring Algorithm)札记

27 9 月, 2014 622点热度 0人点赞 0条评论

在字符串模式匹配算法基础上可以衍生出最长公共子串(Longest Common Substring)算法：假设给出两个字符串S和N，找出二者之间的最大公共子串。

按照正常思路可以很快想到：由大到小依次找出S的所有子串，每次将该子串作为Pattern使用Brute-Force算法搜索字符串N，如果找到匹配，便是最大公共子串。但是这种“算法”的时间复杂度达到O(n3)，严格意义上也不能称之为一种算法，充其量只能算一种人类思维，大部分情况下不应考虑选用这种算法解决问题。

所谓“道不行，乘浮浮于海”。LCS值得推荐的算法有两种：使用动态编程(DP)或者使用后缀数组(suffix array)。

先来看前者，这个算法应该算比较经典的。一般都是先以Fibonacci数列作为DP的入门讲解，之后就会借助这个算法进一步讲解DP的原理，所以这个算法很基本，需要熟练掌握。个人理解，DP本质就是递归，外加一个cache或者table而已。以DP的思维想问题，重点是状态转移方程。本算法的状态转移方程用代码可以表示为“if(i==0||j==0) arr[i][j]=1;else arr[i][j]=arr[i-1][j-1]+1;”理解后准确写出完整的算法代码不难，我写的Java代码如下：

public static ArrayList<String> LCS(String s1,String s2){//written by Yimeng

int[][] arr=new int[s1.length()][s2.length()];

ArrayList<String> lcs=new ArrayList<String>();

int max=0;

for(int i=0;i<s1.length();i++){

for(int j=0;j<s2.length();j++){

if(s1.charAt(i)==s2.charAt(j)){

if(i==0||j==0) arr[i][j]=1;

else arr[i][j]=arr[i-1][j-1]+1;

if(max<arr[i][j]){

max=arr[i][j];

lcs.removeAll(lcs);

lcs.add(s1.substring(i-max+1,i+1));

}

else if(max==arr[i][j]) {lcs.add(s1.substring(i-max+1,i+1));}

}

}

}

return lcs;

}

如果这个算法很熟练了，可以进一步考虑最长公共子序列(Longest Common Subsequence)的算法，从而加深对这类DP问题的理解。

DP方法的时间复杂度为平方阶O(n2)，空间复杂度也是O(n2)，效率有所提高，但却不是最高的算法。利用后缀数组的LCS算法与之相比效率更高，占用空间也更小。

后缀数组是一个处理字符串非常好用的数据结构，本身结构不复杂，但是理解起来比较抽象。概念和理论不在这讨论，想深入了解的话建议阅读论文《后缀数组——处理字符串的有力工具》或其他相关资料。关于后最数组的应用，对sa[],rand[],height[]三个数组的公式关系要理解透彻。使用后缀数组处理字符串会使算法有质的飞跃。这种算法的本质是将求两个字符串的最长公共子串和两个字符串后缀的最长公共前缀的最大值等价，效率得到提升。后缀数组的求法比数组结构本身更重要，其方法有两种：倍增算法和DC3算法，时间复杂度分别为O(nlogn)和O(n)，前者简单一些，后者对我来说太难。我在网上找了一个后缀数组类的C++模版（完整代码），在使用该类的基础上写出的LCS算法如下：

//SuffixArray类为模，使用倍增法构造后缀数组，来源网上

//87行后为LongestCommonString算法，written by Yimeng

#include<cstdio>

#include<cstring>

#include<cmath>

#include <algorithm>

#define FOR(i,a,n) for(int i=a;i<n;++i)

#define REP(i,n) FOR(i,0,n)

using namespace std;

class SuffixArray

{

public:

int *sa,*rank;

int *height;

int keyTypeMax,length;

SuffixArray(int *a,int n,int m)

{

keyTypeMax = max(m,n)+5;

sa = new int[n+10];

rank = new int[keyTypeMax];

height = new int[n+10];

length = n+1;

a[n] = 0;

setSa(a);

setHeight(a);

}

~SuffixArray()

{

delete(sa);

delete(rank);

delete(height);

}

void setSa(int *a)

{

int *cnt = new int[keyTypeMax];

REP(i,keyTypeMax) cnt[i] = 0;

REP(i,length) cnt[rank[i] = a[i]]++;

REP(i,keyTypeMax-1) cnt[i+1] += cnt[i];

for(int i= length-1; i >= 0; i--) sa[--cnt[rank[i]]] = i;

int *rankSt = new int[keyTypeMax];

int *rankStPos = new int[length+10];

for(int p=0,h=1,rankMax=keyTypeMax;

p<length;h<<= 1,rankMax=p)

{

p = 0;

FOR(i,length-h,length) rankStPos[p++] = i;

REP(i,length) if(sa[i]>=h) rankStPos[p++] = sa[i] - h;

REP(i,length) rankSt[i] = rank[rankStPos[i]];

REP(i,rankMax) cnt[i] = 0;

REP(i,length) cnt[rankSt[i]]++;

REP(i,rankMax-1) cnt[i+1] += cnt[i];

for(int i=length-1;i>=0;i--) sa[--cnt[rankSt[i]]] = rankStPos[i];

swap(rank,rankSt);

rank[sa[0]] = 0;

p=1;

FOR(i,1,length)

{

if(rankSt[sa[i]]==rankSt[sa[i-1]]

&&rankSt[sa[i]+h]==rankSt[sa[i-1]+h])

rank[sa[i]] = p-1;

else rank[sa[i]] = p++;

}

}

delete(rankStPos);

delete(rankSt);

delete(cnt);

}

void setHeight(int *a)

{

int h = 0;

REP(i,length)

{

int r = rank[i];

if(!r) height[r] = h = 0;

else

{

int pb = sa[r-1];

int off;

for(off = (h?h-1:0);a[i+off]==a[pb+off];off++) ;

height[r] = h = off;;

}

}

}

};

int main()//written by Yimeng

{

int a[1000],i,first,second;

char s[1000];

scanf("%s",s);

first=strlen(s);

for(i=0;i<first;i++) a[i]=s[i];

a[i]=200;

scanf("%s",s);

second=strlen(s);

for(i=0;i<second;i++) a[first+1+i]=s[i];

SuffixArray sa(a,first+second+1,265);//构建后缀数组

int len=0,flag;

for(i=1;i<sa.length;i++){

int x,y;

x=min(sa.sa[i],sa.sa[i-1]);

y=max(sa.sa[i],sa.sa[i-1]);

if(x<first&&y>first){

if(len<sa.height[i]){

len=sa.height[i];

flag=i;

}

}

}

for(i=0;i<len;i++) printf("%c",a[i+sa.sa[flag-1]]);//打印最小公共串

}

以上代码的时间复杂度为O(nlogn)，空间复杂度为O(n)，若使用DC3算法，其时间复杂度可以优化为线性阶O(n)，不得不由衷地感慨后缀数组之邪恶。

算法还是要以应用为主，毕竟不是学术大牛，不必过于执着于理论，不求甚解也许是更好的境界。最后结论，身为软件工程师，后缀数组算法至少要知其然，DP算法一定要知其所以然。@沂濛

最长公共子串算法(Longest Common Substring Algorithm)札记

文章评论