最长公共子串

✍ dations ◷ 2025-04-04 11:15:11 #算法,动态规划,组合数学

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

字符串"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)} 的时间复杂度内解决.

相关

  • 金巴利金巴利(意大利语:Campari)是一款力娇酒,起源于意大利,根据出售国家不同,起酒精浓度有多个版本,包括20.5%、21%、25%及28%。金巴利使用多种草药和水果酿制,包括厚叶橙(英语:Citrus myrt
  • 梅丽尔·斯特里普梅丽尔·斯特里普(英语:Meryl Louise Streep,1949年6月22日-),美国舞台剧、电影、电视女演员,也是一位慈善家。许多观众与评论家评价她为美国电影史上最伟大的女演员之一,尤其以驾驭
  • 反质子反质子(英语:antiproton)是质子的反粒子,其质量及自旋与质子相同,但电荷及磁矩则与质子相反,带有与电子相同的负电荷。保罗·狄拉克在他的1933年诺贝尔物理学奖演讲中预言反质子的
  • 灌肠 (医学)医学的灌肠(enema)是指通过肛门引液体灌洗直肠的操作。有治疗疾病(例如便秘)、另类保健疗法、减重、或者非法虐待(例如性虐待)的用途。使用的器具及液体必须为医用,否则很容易引发
  • 亨利·德雷伯亨利·德雷伯(Henry Draper,1837年3月7日-1882年11月20日),美国医生、天文学家,天体摄影的先驱。亨利·德雷伯的父亲约翰·威廉·德雷伯是一位医生、化学家、植物学家,是纽约大学的
  • 钓虾钓虾(英语:Prawning, prawn fishing)是一种垂钓休闲活动,在台湾、马来西亚、新加坡、泰国等地都很流行,钓虾活动可以在野外的溪流、河口或人工养殖场进行。钓虾在台湾已有30年历
  • 伍德维尔 (阿拉巴马州)伍德维尔(英文:Woodville),是美国阿拉巴马州下属的一座城市。面积约为6.62平方英里(约合 17.15平方公里)。根据2010年美国人口普查,该市有人口746人,人口密度为112.65/平方英里(约合4
  • 陆贾陆贾(前240年-前170年),楚人。西汉初期的政治家、文学家、思想家,对早期道家的发展有重要作用。按《陈留风俗传》的记载,春秋时陆浑被晋国消灭后,该国国君投奔楚国,陆贾就是陆浑国君
  • 比斯库·贝洛比斯库·贝洛(匈牙利语:Biszku Béla,1921年9月13日-2016年3月31日),匈牙利索博尔奇-索特马尔-贝拉格州马罗克保皮人,匈牙利政治人物,曾任匈牙利社会主义工人党中央政治局委员、中央
  • 岸田今日子岸田今日子(日语:岸田 今日子,1930年4月29日-2006年12月17日),日本女演员、配音员、童话作家。身高156cm。A型血。1930年4月29日出生于东京府豊多摩郡(今东京都杉并区),父亲是剧作家