再谈最长公共子串问.doc

《再谈最长公共子串问.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、再谈最长公共子串问题作者：寒雨疏桐文章来源：网易点击数：1049更新时间：12/30/2003    最长公共子串（Longest common substring, 简称LCS）问题指的是求出给定的一组字符串的长度最大的共有的子字符串。    举例说明，以下三个字符串的LCS就是 cde：    abcde     cdef     ccde         高效的查找LCS算法可以用于比较多篇文章的最长相同片段，以及生物学上的基因比较等实际应用。    前几天写了一个穷举法的简单实现，感觉在数据量稍大时效率极低，所以今天上网查了一些资料，找

2、到了解决LCS问题的最佳算法并编程实现，程序效率得到了极大的提高。    采用的是广义后缀树（Generalized Suffix Tree，简称GST)算法，就是把给定的N个源字符串的所有的后缀建成一颗树，这个树有以下一些特点：    1.树的每个节点是一个字符串，树根是空字符串“”    2.任意一个后缀子串都可以由一条从根开始的路径表达     （将这条路径上的节点字符串依次拼接起来就可以得到这个后缀）    3.特别应注意任意一个子串都可以看作某一个后缀的前缀。既然每一个后缀      都可以由一条从根开始的路径表达，那么我们可以从根节

3、点开始一个字符      一个字符的跟踪这条路径从而得到任意一个子串。    4.为了满足查找公共子串的需求，每个节点还应该有从属于哪个源字符串的      信息    由以上的定义我们不难看出，在这棵GST树上，如果找到深度最大并且从属于所有源字串的节点，那么，把从根到这个节点的路径上的所有节点字符串拼接起来就是LCS。        还是举例说明，上面提到的三个字符串【abcde cdef ccde】的所有后缀子串列表如下：(注：.1表示是从第一个串abcde来的，同理.2,.3分别表示从cdef，ccde来的)        abcde.

4、1    bcde.1    cde.1    de.1    e.1    cdef.2    def.2    ef.2    f.2    ccde.3    cde.3    de.3    e.3        建成的GST如下图所示(注:.1表示从属于第一个串，.123表示既从属于第一又从属于第二，第三个源串）       --_______【abcde.1】                  

5、                                  

6、_____【bcde.1】         .....最深的并且带

7、.123的节点         

8、                        :         

9、_____【c.123】____【de.123】_______【f.2】         

10、               

11、         

12、               

13、__【cde.3】         

14、         

15、_____【de.123】___【f.2】         

16、         

17、_____【e.123】____【f.2】         

18、         

19、_____【f.2】             上

20、图中虚线所指的【de.123】节点所表示的子串cde正是LCS        以上是一些基本概念，但是实际应用时还要涉及到构建GST树以及查找LCS的具体算法，参考了网上的一些资料，我用java语言实现了这些算法，基本上可以以O(n)的时间复杂度进行建树及查找处理。    如果对构建SuffixTree算法等细节感兴趣，可以到google上查阅相关资料。        我的Java源程序如下：*******************主程序LongestCommonSubstring.java***********import java.io.*;

21、import java.util.*;class LongestCommonSubstring {    //============================================    //Creight Suffix Tree 构建算法    //要求字符串结尾是一个在字符串中没有出现过的    //一个字符，所以选择了'00'到'03'等几个字符，    //如果源字串中出现了这几个特殊    //字符，程序将不能正常运行    //========================================

22、====    static String seprator[] =         {""+'', ""+'1', ""+'2', ""+'