最长公共子串

✍ dations ◷ 2025-06-29 03:09:32 #算法,动态规划,组合数学

在计算机科学中,最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是。

字符串"ABABC","BABCA"以及"ABCBA"的最长公共子串是"ABC"。其他的公共子串包括"A"、"AB"、"B"、"BA"、"BC"以及"C"。

  ABABC    |||   BABCA    |||    ABCBA

问题定义

给定两个字符串,长度为 m {\displaystyle m} 的字符串 S {\displaystyle S} 以及长度为 n {\displaystyle n} 的字符串 T {\displaystyle T} ,求最长的子串 x {\displaystyle x} 同时是 S {\displaystyle S} 以及 T {\displaystyle T} 的连续子串。

问题可以一般化为k-公共子串问题——给定字符串的集合 S = { S 1 , . . . , S K } {\displaystyle {\displaystyle S=\{S_{1},...,S_{K}\}}} ,其中 | S i | = n i {\displaystyle |S_{i}|=n_{i}} Σ n i = N {\displaystyle \Sigma n_{i}=N} .。对于满足 2 k K {\displaystyle 2\leq k\leq K} k {\displaystyle k} ,找出至少是 S {\displaystyle S} k {\displaystyle k} 个字符串的公共子串的最长串。

利用广义后缀树,我们可以在 Θ ( n + m ) {\displaystyle \Theta (n+m)} 的时间复杂度内求出 S {\displaystyle S} T {\displaystyle T} 的最长公共子串的长度和他们的起始位置。而如果利用动态规划求解,则时间复杂度为 Θ ( n m ) {\displaystyle \Theta (nm)} 。而对于一般化的公共子串问题,使用动态规划的求解的时间复杂度为 Θ ( n 1 {\displaystyle \Theta (n_{1}} ·...· n K ) {\displaystyle n_{K})} ,利用广义后缀树则需 Θ ( N K ) {\displaystyle \Theta (N*K)} 的时间复杂度。

字符串集合的最长公共子串可以通过构造一棵广义后缀树, 然后去查找拥有来自所有集合中字符串的叶节点的最深的内部节点来得到。右图展示了字符串“ABAB”,“BABA”和“ABBA”对应的广义后缀树。为了方便后缀树的构造和区分字符串,每个串的结尾都添加了终结符“$”和字符串编号,分别变成了“ABAB$0”,“BABA$1”和 “ABBA$2”。如图所示,串“A”,“B”,“AB”和“BA”的节点对应的子树都包含来自所有字符串的叶节点。

假定字母表的大小是常数,构造这样的一颗后缀树的时间复杂度为 Θ ( N ) {\displaystyle \Theta (N)} 。这样,如果将整个树自底向上遍历,并在每个节点通过一个位向量标记每个节点的子树中出现过的所有字符串的,则k-公共子串问题可以以 Θ ( N K ) {\displaystyle \Theta (NK)} 的时间复杂度来解决。特别地,如果后缀树为常数时间的最近公共祖先检索做了优化,那么问题将可以在 Θ ( N ) {\displaystyle \Theta (N)} 的时间复杂度内解决.

相关

  • 新美鞭菌新美鞭菌属是新美鞭菌门新美鞭菌科真菌的一属。其学名来自古希腊语词根neo-(新)、calli-(美丽)和mastix(鞭)。“新美鞭菌属”系台湾生物多样性资讯入口网所采用的中文名。
  • 澳大利亚陆军澳大利亚陆军(Australian Army),为澳大利亚的陆上武装部队。与皇家澳大利亚海军、皇家澳大利亚空军构成澳大利亚的国防力量。澳大利亚陆军沿袭自英国陆军。大致可分成两个时期
  • 朴素淡朴素谈(韩语:박소담,1991年9月8日-),又译朴素淡、朴素丹,韩国女演员。毕业于韩国艺术综合大学演剧系,2013年参与电影演出,进入演艺圈。
  • 地中海猕猴巴巴利猕猴(学名:Macaca sylvanus),又称为叟猴、地中海猕猴或直布罗陀猿,是一种尾部退化的猕猴。该物种分布在阿特拉斯山脉的阿尔及利亚和摩洛哥,在直布罗陀有少量分布,可能为引进
  • 第三航空舰队第三航空舰队(日语:第三航空艦隊/だいさんこうくうかんたい Daisan Kōkū Kantai ?)是旧日本海军在太平洋战争末期组建的一支陆基海军航空兵编制。此时盟军反攻的前锋已经抵
  • 霸权霸权或霸权主义(英语:Hegemony或Hegemonism),是指一国凭借其政治、军事和经济的极大优势,在全世界或个别地区控制他国主权、主导国际事务或谋求统治地位的政策的意识形态。在公元
  • 天鹅龙虾天鹅龙虾(学名:Panulirus cygnus)是分布在澳洲西部的一种龙虾。它们是澳洲最有价值的渔获,占了全澳洲总渔业价值的20%。天鹅龙虾有5对脚,雌虾的第5对脚有爪,在口部有6对较为细小的
  • 尼古拉伊·波多罗夫尼古拉伊·波多罗夫(保加利亚语:Николай Бодуров;;1986年5月30日-)是一位保加利亚足球运动员,在场上的位置是右后卫。他现在效力于英格兰足球冠军联赛球队富勒姆足
  • 成德成德又名恒冀或镇冀,唐代地名,治所在恒州(今河北省石家庄市正定县)。唐代安史之乱之后,李宝臣领成德节度使,统治河北中部,是当时的不服从唐朝中央政府的藩镇割据局势中实力最强的河
  • 纳粹飞碟纳粹飞碟(英语:Nazi UFO)是知名的都市传说之一。在第二次世界大战期间,希特勒想对付盟军令纳粹德国扭转败局,下令纳粹德国科学家秘密研制的一种圆碟形状的飞行器,然而目前所有传说