最长公共子串

✍ dations ◷ 2025-04-26 12:20:34 #算法,动态规划,组合数学

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

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

相关

  • 上海体育学院上海体育学院是中华人民共和国成立后创建的第一所体育高等学府,建于1952年11月8日,原名华东体育学院,由华东师范大学、南京大学和金陵女子大学等院校的体育系科合并而成;1956年2
  • 630110 数学 120 信息科学与系统科学 130 力学 140 物理学 150 化学 160 天文学 170 地球科学 180 生物学210 农学 220 林学 230 畜牧、兽医科学 240 水产学310 
  • 李德平李德平(1926年11月4日-),生于北京,籍贯江苏兴化市,中国辐射物理、辐射防护及安全学家。1948年毕业于清华大学物理系。1991年当选为中国科学院学部委员(院士)。中国辐射防护研究院研
  • 滑坡滑坡是在自然地质作用和人类活动的影响下,斜坡上的岩土体在重力作用下沿一定的软弱面向下滑动的现象及其形成的地貌形态。在斜性变形破坏的地质灾害中,滑坡分布广、发生概率高
  • 儿童性别不安儿童性别不安(英语:Gender dysphoria in children),也称为儿童性别认同障碍(英语:gender identity disorder in children)或儿童性别不一致(英语:gender incongruence of childhood),是
  • 第二次巴巴利战争第二次巴巴利战争(The Second Barbary War),又名阿尔及利亚战争(Algerian War),是指美国与北非巴巴利地区的第二次战争。第二次巴巴利战争(1815年),也被称为阿尔及利亚战争,是美国与统
  • 社会主义替代社会主义替代(英语:Socialist Alternative)是美国的一个托洛茨基主义政党。该党成立于1986年,当时取名为劳工战斗者。1990年代末,该党改用现名。该党的意识形态是社会主义、马克
  • 非洲灵猫属非洲灵猫(学名:Civettictis civetta)是非洲热带的麝猫。它们不像其他灵猫科般像猫,反而像短小的狗。它们的毛粗糙,有黑点及白间,面部呈白色,眼睛有黑斑及淡色的吻。它们的肛腺,可以
  • 第3周期元素第3周期元素是元素周期表中第三行(即周期)的元素。含有:
  • 绿豆椪绿豆椪是台式的传统月饼,因外型圆凸而称为“椪”,内馅是由绿豆泥甜馅抹猪油及红葱头烘烤制成,有时还会加入少许猪肉。近年由于较重视健康,许多业者也推出不含猪肉、猪油等材料,纯