文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 求最长公共子串问题的算法分析
侵权投诉

求最长公共子串问题的算法分析

最长公共子串问题

  第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是字符

第1页

你可能喜欢

热门文档

相关文档

  • 最长公共子序列算法分析

    最长公共子序列算法分析_合同协议_表格/模板_应用文书。算法求连续的最长公共子串 ? 首先我们来分析一个简单例子。 首先我们来分析一个简单例子。 ? 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)当输入的两个字符串...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email