最长公共子串

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

  ABABC
    |||
   BABCA
    |||
    ABCBA

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

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

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

利用广义后缀树

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

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

1. ^ Gusfield, Dan. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. 1999 [1997]. ISBN 0-521-58519-8.