最长公共子串问题
第24卷 第12期
文章编号:1006-9348(2007)12-0097-04
计 算 机 仿 真
2007年12月
求最长公共子串问题的算法分析
张毅超,车玫,马骏
(中国航天科技集团公司第710研究所,北京100037)
摘要:高效求解2个字符串的最长公共子串(LongestCommonSubstring)是实现很多字符串算法的关键。文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树算法的时间复杂度较低,但实现较为复杂并且广义后缀树占用的空间也较多。最后提出了一个新算法,该算法使用2个字符串的广义后缀数组,在保持和广义后缀树时间复杂度相等的基础上,可以简单地实现并且占用较少的空间。关键词:最长公共子串;动态规划;广义后缀树;广义后缀数组中图分类号:TP30116 文献标识码:A
AnalysisoftheLongestCommonSubstringAlgorithm
ZHANGYi-chao,M(The710InstituteofChinaAerospaceScienceand)ABSTRACT:Howtosolvethelongesttisthekeytomanystringalgorithms.Firstlythisproblem.Oneisthedynamicprogramming(DP)algorithm,(GST)algorithm.TheDPalgorithmiseasytoimplement,lexity.ThetimecomplexityofGSTalgorithmislow,howeveritneedsmuchmoretricktoiandtakesmuchstoragespace.Attheend,thispapershowsageneralizedsuffixarray(GSA)algorithmwhichhasthesametimecomplexityastheGSAalgorithmandtakeslessstoragespacethanGSTalgorithm.
KEYWORDS:Longestcommonsubstring;Dynamicprogramming;Generalizedsuffixtree;Suffixarray
Suffix(S,i),也就是Suffix(S,i)=S[i..len(S)]。
公共子串(commonsubstring)字符串U如果既是字符
1 引言
解决最长公共子串(LongestCommonSubstring)问题的算法是计算机处理数据的一个基础算法,简单高效的LCS算法可以解决很多应用问题,例如:比较分析Web页面内容的最长相同部分,以及生物学上的基因比较等实际应用。
基本定义:
字符串(string)一个字符串S是将n个字符顺次排列形成的数组,n称为S的长度,表示为len(S)。S的第i字符表示为S[i]。
子串(substring)字符串S的子串S[i..j],i≤j,表示S串中从i到j这一段,也就是顺次排列S[i],S[i+1],…,S[j]形成的字符串。
后缀(suffix)后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为
收稿日期:2006-11-14 修回日期:2006-11-27
串S的子串又是字符串T的子串,则字符串U是字符串S
和T的一个公共子串。
最长公共子串(LongestCommonSubstring)字符串S和T的最长公共子串是指字符串S和T的所有公共后缀中长度最大的后缀。
例如:给定3个长度分别为4,4的字符串“abab”,“baba”,它们的公共子串(CommonSubstring)有“”,“a”,“b”,“ab”,“ba”,“aba”,“bab”。其中最长公共子串(LCS)即为“aba”或“bab”。
2 动态规划算法
动态规划算法是解决最长公共子串问题的经典算法之一。
基本定义:
公共后缀(LongestCommonSuffix)字符串U如果既是字符串S的后缀又是字符串T的后缀,则字符串U是字符
最长公共子序列算法分析_合同协议_表格/模板_应用文书。算法求连续的最长公共子串 ? 首先我们来分析一个简单例子。 首先我们来分析一个简单例子。 ? LCS(‘...
动态规划求解最长公共子串问题 算法思想 求字符串 str1,str2 的最长公共子串的长度。 定义二元函数函数 f(m,n):分别以 str1[m],str2[n]结尾的连续公共...
两种基于双向比较的最长公共子串算法_数学_自然科学_专业资料。■ 研0E王8—...(LCSstr)是 一类 重要字 符 串分析 问题 ,在 字符 串近 似 匹配 、计 算...
分析描述LCS问题最优解的结构 首先.我们给出一个...在下一次计算中,就会遇到 <A,B,C>与<>。显然,...进一步练习求最长公共子串的最优解的形成(巴蜀1598...
利用动态规划算法解决最... 4页 1下载券 实验二...求解最长公共子串...本文分析了供应链节点企业冲突的特 征,存在的原因...
动态规划求解最长公共子串问题 算法思想 求字符串str1,str2的最长公共子串的...时间空间复杂度分析 如果用n,m表示两个字符串的长度的话,那么算法的 时间复杂...
最长公共子串(Longest common substring, 简称 LCS)问题指的是求出给定的一组...采用的是广义后缀树(Generalized Suffix Tree,简称 GST)算法,就是把给定的 N ...
动态规划求解最长公共子串问题 算法思想 求字符串str1,str2的最长公共子串的长度。 定义二元函数函数f(m,n):分别以str1[m],str2[n]结尾的连续公共子串...
最长公共子序列算法分析实验报告_IT/计算机_专业...一、 实验目的: (1)能够熟悉最长公共子序列问题...字符串没有公共子序列时: (2)当输入的两个字符串...
热门文档