后缀自动机 (SAM)

后缀自动机 是一个能解决许多字符串相关问题的有力的数据结构。

举个例子，字符串问题：

在另一个字符串中搜索一个字符串的所有出现位置。
计算给定的字符串中有多少个不同的子串。

以上问题都可以在线性的时间复杂度内通过后缀自动机来实现。

直观上，字符串的后缀自动机可以理解为给定字符串的 所有子串 的压缩形式。值得注意的事实是，后缀自动机将所有的这些信息以高度压缩的形式储存。对于一个长度为的字符串，它的空间复杂度仅为。此外，构造后缀自动机的时间复杂度仅为（这里我们将字符集的大小看作常数，否则时间复杂度和空间复杂度均为）。

后缀自动机的定义¶

给定字符串的后缀自动机是一个接受所有字符串的后缀的最小 DFA （确定性有限自动机或确定性有限状态自动机）。

换句话说：

后缀自动机是一张有向无环图。顶点被称作状态，边被称作状态间的转移。
一个状态为 初始状态 ，它必定为这张图的源点（其它各点均与连通）。
每个转移都标有一些字母。从一个顶点出发的所有转移均不同。
一个或多个状态为 终止状态 。如果我们从初始状态出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是字符串的一个后缀。的每个后缀均可用一条从到一个终止状态的路径构成。
后缀自动机是所有满足上述条件的自动机中顶点数最少的一个。

子串的性质¶

后缀自动机最简单和最重要的性质是，它包含关于字符串的所有子串的信息。任意从初始状态开始的路径，如果我们将转移路径上的标号写下来，都会形成的一个子串。反之每个的子串对应于从开始的某条路径。

为了简化表达，我们将会说子串 对应于 一条路径（从开始且一些标号构成这个子串）。反过来我们说任意一条路径 对应于 它的标号构成的字符串。

一条或多条路径可以到达一个状态，因此我们说一个状态对应于字符串的集合，这也对应于那些路径。

构造后缀自动机的实例¶

我们将会在这里展示一些简单的字符串的后缀自动机。

我们用蓝色表示初始状态，用绿色表示终止状态。

对于字符串：

在线性时间内构造后缀自动机¶

在我们描述线性时间内构造后缀自动机的算法之前，我们需要引入几个对理解构造过程非常重要的新概念并简单证明。

结束位置¶

考虑字符串的任意非空子串，我们记为在字符串中的所有结束位置（假设对字符串中字符的编号从零开始）。例如，对于字符串，我们有。

当两个子串与的末尾集合相等时我们称它们是等价的：即。这样所有字符串的非空子串都可以根据它们的集合被分为几个 等价类 。

显然，在后缀自动机中的每个状态对应于一个或多个相同的子串。换句话说，后缀自动机中的状态数等于所有子串的等价类的个数，加上初始状态。后缀自动机的状态个数等价于相同的一个或多个子串所组成的集合的个数。

我们稍后将会用这个假设介绍构造后缀自动机的算法。在那时我们将会发现，后缀自动机需要满足的所有性质，除了最小性以外都满足了。由 Nerode 定理我们可以得出最小性（这篇文章不会证明后缀自动机的最小性）。

由的值我们可以得到一些重要结论：

引理 1： 当且仅当字符串以的一个后缀的形式出现在字符串中时，两个非空子串和（假设）是等价的。

引理显然成立。如果和的相同，则是的一个后缀，且只以中的一个的后缀的形式出现。且根据定义，如果为的一个后缀，且只以后缀的形式在中出现时，两个子串的值相等。

引理 2： 考虑两个非空子串和（假设）。则它们的构成的集合要么完全没有交集，要么是的一个子集。并且这依赖于是否为的一个后缀。即：

证明：如果集合与有至少一个公共元素，那么由于字符串与都在一个位置结束，即是的一个后缀。但是如果如此在每次出现的位置子串也会出现，这意味着是的一个子集。

引理 3： 考虑一个等价类。将类中的所有子串按长度非递增的顺序排序。即每个子串都会比它前一个子串短，与此同时每个子串也是它前一个子串的一个后缀。换句话说，同一等价类中任两子串中较短者为较长者后缀，且该类中的子串长度恰好覆盖整个区间。

证明：固定一些等价类。如果等价类中只包含一个子串，引理显然成立。现在我们来讨论子串元素个数大于的等价类。

由引理 1，两个不同的等价字符串中较短的一个总是较长的一个的真后缀。因此，等价类中不可能有两个等长的字符串。

记为等价类中最长的字符串，类似地，记为等价类中最短的字符串。由引理 1，字符串是字符串的真后缀。现在考虑长度在区间中的的任意后缀。容易看出，这个后缀也在同一等价类中。因为这个后缀只能在字符串中以的一个后缀的形式存在（也因为较短的后缀在中只以的后缀的形式存在）。因此，由引理 1，这个后缀与字符串等价。

后缀链接¶

考虑后缀自动机中满足的一些状态。我们已经知道，状态对应于具有相同的等价类。我们如果定义为这些字符串中最长的一个，则所有其它的字符串都是的后缀。

我们还知道字符串的前几个后缀（如果我们用长度降序考虑这些后缀）在这个等价类中全部被包含，且所有其它后缀（至少一个—空后缀）在其它的等价类中。我们记为最大的这样的后缀，然后用后缀链接连到上。

换句话说，一个 后缀链接 连接到对应于的最长后缀的另一个等价类的状态。

以下我们假设初始状态对应于它自己这个等价类（只包含一个空字符串），为了方便我们规定。

引理 4： 所有后缀链接构成一棵根节点为的树。

证明：考虑任意满足的状态，一个后缀链接连接到的状态对应于严格更短的字符串（根据后缀链接的定义和引理 3）。因此，通过在后缀链接上移动，我们早晚会到达对应空串的初始状态。

引理 5： 如果我们使用集合构造一棵树（所有子节点的集合为父节点的子集），则这个结构由后缀链接连接起来。

证明：由引理 2，我们可以用集合构造一棵树（因为两个集合要么完全没有交集要么其中一个是另一个的子集）。

我们现在考虑任意满足的状态和它的后缀链接，由后缀链接和引理 2，我们可以得到

，这与前面的引理证明了以下断言成立：后缀链接构成的树本质上是集合构成的一棵树。

以下是对于字符串构造后缀自动机时产生的后缀链接树的一个例子，节点被标记为对应等价类中最长的子串。

小结¶

在学习算法本身前，我们对之前学过的知识进行一下总结，并引入一些辅助记号。

的子串可以根据它们结束的位置被划分为多个等价类；
后缀自动机由初始状态和与每一个等价类对应的每个状态组成；
对于每一个状态，一个或多个子串与之匹配。我们记为其中最长的一个字符串，记为它的长度。类似地，记为最短的子串，它的长度为。那么所有对应这个状态的所有字符串都是字符串的不同的后缀，且所有字符串的长度恰好覆盖区间中的每一个整数。
对于任意满足的状态，定义后缀链接为连接到对应字符串的长度为的后缀的一条边。从根节点出发的后缀链接可以形成一棵树，与此同时，这棵树形成了集合间的包含关系。
我们可以对的状态使用后缀链接解释如下：

如果我们从任意状态开始顺着后缀链接遍历，早晚都会到达初始状态。这种情况下我们可以得到一个互不相交的区间的序列，且它们的并集形成了连续的区间。

算法¶

现在我们可以学习算法本身了。这个算法是在线算法，这意味着我们可以逐个加入字符串中的每个字符，并且在每一步中对应地维护后缀自动机。

为了保证线性的空间复杂度，我们将只保存和的值和每个状态的一个转移列表，我们不会标记终止状态（但是我们稍后会展示在构造后缀自动机后如何分配这些标记）。

一开始后缀自动机只包含一个状态，编号为（其它状态的编号为）。为了方便，我们分配给它和（表示一个虚拟的不存在的状态）。

现在整个任务转化为实现给当前字符串添加一个字符的过程。算法流程如下：

令为对应添加字符之前的整个字符串（一开始我们设置且我们会在算法的最后一步对应地更新）。
创建一个新的状态，并将赋值为，在这时的值还未知。
现在我们按以下流程进行：我们从状态开始。如果还没有到字符的转移，我们就添加一个到状态的转移，遍历后缀链接。如果在某个点已经存在到字符的转移，我们就停下来，并将这个状态标记为。
如果没有找到这样的状态，我们就到达了虚拟状态，我们将赋值为并退出。
假设现在我们找到了一个状态，其可以转移到字符，我们将这个状态转移到的状态标记为。
现在我们分类讨论两种状态，要么，要么不是。
如果，我们只要将赋值为并退出。
否则就会有些复杂。需要复制状态：我们创建一个新的状态，复制的除了的值以外的所有信息（后缀链接和转移）。我们将赋值为。
复制之后，我们将后缀链接从指向，也从指向。
最终我们需要使用后缀链接从状态返回，因为存在一条通过到状态的转移，并在此过程中重定向所有状态到状态。
以上三种情况，在完成这个过程之后，我们将的值更新为状态。

如果我们还想知道哪些状态是 终止状态 而哪些不是，我们可以在为字符串构造完完整的后缀自动机后找到所有的终止状态。为此，我们从对应整个字符串的状态（存储在变量中），遍历它的后缀链接，直到到达初始状态。我们将所有遍历到的节点都标记为终止节点。容易理解这样做我们会精确地标记字符串的所有后缀，这些状态恰好是终止状态。

在下一部分，我们将观察算法每一步的细节，并证明它的 正确性 。

现在，我们只注意到，因为我们只为的每个字符创建一个或两个新状态所以后缀自动机只包含 线性个 状态。

转移个数是线性规模的，以及总体上算法的运行时间是线性规模的，这两点还不那么清楚。

正确性证明¶

若一个转移满足则我们称这个转移是 连续的 。否则，即当时，这个转移被称为 不连续的 。从算法描述中可以看出，连续的和非连续的转移是算法的不同情况。连续的转移是固定的，我们不会再改变了。与此相反，当向字符串中插入一个新的字符时，非连续的转移可能会改变（转移边的端点可能会改变）。
为了避免引起歧义，我们记向后缀自动机中插入当前字符之前的字符串为。
算法从创建一个新状态开始，对应于整个字符串。我们创建一个新的节点的原因很清楚。与此同时我们也创建了一个新的字符和一个新的等价类。
在创建一个新的状态之后，我们会从对应于整个字符串的状态通过后缀链接进行遍历。对于每一个状态，我们尝试添加一个从字符到新状态的转移。然而我我们只能添加与原来已存在的转移不冲突的转移。因此我们只要找到已存在的的转移，我们就必须停止。
最简单的情况是我们到达了虚拟状态，这意味着我们为所有的后缀添加了的转移。这也意味着，字符从未在字符串中出现过。因此的后缀链接为状态。
第二种情况下，我们找到了现有的转移。这意味着我们尝试向自动机内添加一个 已经存在的 字符串（其中为的一个后缀，且字符串已经作为的一个子串出现过了）。因为我们假设字符串的自动机的构造是正确的，我们不应该在这里添加一个新的转移。然而，有一个难点。从状态出发的后缀链接应该连接到哪个状态呢？我们要把后缀链接连到一个状态上，且其中最长的一个字符串恰好是，即这个状态的应该是。然而还不存在这样的状态，即。这种情况下，我们必须要通过拆开状态来创建一个这样的状态。
如果转移是连续的，那么。在这种情况下一切都很简单。我们只需要将的后缀链接指向状态。
否则转移是不连续的，即，这意味着状态不只对应于长度为的后缀，还对应于的更长的子串。除了将状态拆成两个子状态以外我们别无他法，所以第一个子状态的长度就是了。
我们如何拆开一个状态呢？我们复制状态，产生一个状态，我们将赋值为。由于我们不想改变遍历到的路径，我们将的所有转移复制到。我们也将从出发的后缀链接设置为的后缀链接的目标，并设置的后缀链接为。
在拆开状态后，我们将从出发的后缀链接设置为。
最后一步我们将一些到转移重定向到。我们需要修改哪些转移呢？只重定向相当于所有字符串（其中是的最长字符串）的后缀就够了。即，我们需要继续沿着后缀链接遍历，从顶点直到虚拟状态或者是转移到不是状态的一个转移。

对操作次数为线性的证明¶

首先我们假设字符集大小为常数。如果字符集大小不是常数，后缀自动机的时间复杂度就不是线性的。从一个顶点出发的转移存储在支持快速查询和插入的平衡树中。因此如果我们记为字符集的大小，则算法的渐进时间复杂度为，空间复杂度为。然而如果字符集足够小，可以不写平衡树，以空间换时间将每个顶点的转移存储为长度为的数组（用于快速查询）和链表（用于快速遍历所有可用关键字）。这样算法的时间复杂度为，空间复杂度为。

所以我们将认为字符集的大小为常数，即每次对一个字符搜索转移、添加转移、查找下一个转移—这些操作的时间复杂度都为。

如果我们考虑算法的各个部分，算法中有三处时间复杂度不明显是线性的：

第一处是遍历所有状态的后缀链接，添加字符的转移。
第二处是当状态被复制到一个新的状态时复制转移的过程。
第三处是修改指向的转移，将它们重定向到的过程。

我们使用后缀自动机的大小（状态数和转移数）为 线性的 的事实（对状态数是线性的的证明就是算法本身，对转移数为线性的的证明将在稍后实现算法后给出）。

因此上述 第一处和第二处 的总复杂度显然为线性的，因为单次操作均摊只为自动机添加了一个新转移。

还需为 第三处 估计总复杂度，我们将最初指向的转移重定向到。我们记，这是一个字符串的后缀，每次迭代长度都递减—因为作为字符串的位置随着每次迭代都单调上升。这种情况下，如果在循环的第一次迭代之前，相对应的字符串在距离的深度为的位置上（深度记为后缀链接的数量），那么在最后一次迭代后，字符串将会成为路径上第二个从出发的后缀链接（它将会成为新的的值）。

因此，循环中的每次迭代都会使作为当前字符串的后缀的字符串的位置单调递增。因此这个循环最多不会执行超过次迭代，这正是我们需要证明的。

实现¶

首先，我们描述一种存储一个转移的全部信息的数据结构。如果需要的话，你可以在这里加入一个终止标记，也可以是一些其它信息。我们将会用一个 map 存储转移的列表，允许我们在总计的空间复杂度和的时间复杂度内处理整个字符串。

struct state {
  int len, link;
  map<char, int> next;
};

后缀自动机本身将会存储在一个 state 结构体数组中。我们记录当前自动机的大小 sz 和变量 last ，当前整个字符串对应的状态。

1
2
3

const int MAXLEN = 100000;
state st[MAXLEN * 2];
int sz, last;

我们定义一个函数来初始化后缀自动机（创建一个只有一个状态的后缀自动机）。

void sa_init() {
  st[0].len = 0;
  st[0].link = -1;
  sz++;
  last = 0;
}

最终我们给出主函数的实现—给当前行末增加一个字符，对应地重建自动机。

void sa_extend(char c) {
  int cur = sz++;
  st[cur].len = st[last].len + 1;
  int p = last;
  while (p != -1 && !st[p].next.count(c)) {
    st[p].next[c] = cur;
    p = st[p].link;
  }
  if (p == -1) {
    st[cur].link = 0;
  } else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len) {
      st[cur].link = q;
    } else {
      int clone = sz++;
      st[clone].len = st[p].len + 1;
      st[clone].next = st[q].next;
      st[clone].link = st[q].link;
      while (p != -1 && st[p].next[c] == q) {
        st[p].next[c] = clone;
        p = st[p].link;
      }
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}

正如之前提到的一样，如果你用内存换时间（空间复杂度为，其中为字符集大小），你可以在的时间内构造字符集大小任意的后缀自动机。但是这样你需要为每一个状态储存一个大小为的数组（用于快速跳转到转移的字符），和另外一个所有转移的链表（用于快速在转移中迭代）。

应用¶

下面我们来看一下一些可以用后缀自动机解决的问题。为了简单，我们假设字符集的大小为常数，允许我们认为增加一个字符和遍历的复杂度为常数。

检查字符串是否出现¶

给一个文本串和多个模式串，我们要检查字符串是否作为的一个子串出现。

我们在的时间内为文本串构造后缀自动机。为了检查模式串是否在中出现，我们沿转移（边）从开始根据的字符进行转移。如果在某个点无法转移下去，则模式串不是的一个子串。如果我们能够这样处理完整个字符串，那么模式串在中出现过。因此

对于每个字符串算法的时间复杂度为。此外，这个算法还找到了模式串在文本串中出现的最大前缀长度。

不同子串个数¶

给一个字符串，计算不同子串的个数。

为字符串构造后缀自动机。

每个的子串都相当于自动机中的一些路径。因此不同子串的个数等于自动机中以为起点的不同路径的条数。

考虑到后缀自动机为有向无环图，不同路径的条数可以使用动态规划计算。

即，令为从状态开始的路径数量（包括长度为零的路径），则我们有如下递推方程式：

即，可以表示为所有的转移的末端的和。

所以不同子串的个数为（因为要去掉空子串）。

总时间复杂度为：。

所有不同子串的总长度¶

给定一个字符串，计算所有不同子串的总长度。

本题做法与上一题类似，只是现在我们需要考虑分两部分进行动态规划：不同子串的数量和它们的总长度。

我们已经在上一题中介绍了如何计算。的值可以使用通过以下递推式计算：

我们取每个邻接顶点的答案，并加上（因为从状态出发的子串都增加了一个字符）。

算法的时间复杂度仍然是。

字典序第大子串¶

给定一个字符串。多组询问，每组询问给定一个数，查询所有子串中字典序第大的子串。

解决这个问题的思路基于前两个问题的思路。字典序第大的子串对应于后缀自动机中字典序第大的路径。因此在计算每个状态的路径数后，我们可以很容易地从后缀自动机的根开始找到第大的路径。

预处理的时间复杂度为，单次查询的复杂度为（其中是查询的答案，为字符集的大小）。

最小循环移位¶

给定一个字符串。找出字典序最小的循环移位。

我们为字符串构造后缀自动机。则后缀自动机本身将包含字符串的所有循环移位作为路径。

所以问题简化为寻找最小的长度为的路径，这可以通过平凡的方法做到：我们从初始状态开始，贪心地访问最小的字符即可。

总的时间复杂度为。

出现次数¶

对于一个给定的文本串，有多组询问，每组询问给一个模式串，回答模式串在字符串中作为子串出现了多少次。

我们为文本串构造后缀自动机。

接下来我们做以下的预处理：对于自动机中的每个状态，预处理值等于这个集合大小的。事实上对应于同一状态的所有子串在文本串中的出现次数相同，这相当于集合中的位置数。

然而我们不能明确的构造集合，因此我们只考虑它们的大小。

为了计算这些值，我们进行以下操作。对于每个状态，如果它不是通过复制创建的（且它不是初始状态），我们用初始化它。然后我们按它们的长度降序遍历所有状态，并将当前的的值加到后缀链接上，即：

这样做每个状态的答案都是正确的。

为什么这是正确的？不是通过复制获得的状态，恰好有个，并且它们中的前个在我们插入前个字符时产生。因此对于每个这样的状态，我们在它被处理时计算它们所对应的位置的数量。因此我们初始将这些状态的的值赋为，其它状态的值赋为。

接下来我们对每一个执行以下操作：。其背后的含义是，如果有一个字符串出现了次，那么它的所有后缀也在完全相同的地方结束，即也出现了次。

为什么我们在这个过程中不会重复计数（即把某些位置数了两次）呢？因为我们只将一个状态的位置添加到一个其它的状态上，所以一个状态不可能以两种不同的方式将其位置重复地指向另一个状态。

因此，我们可以在的时间内计算出所有状态的的值。

最后回答询问只需要查找查找值，其中为如果存在这样的状态就是状态对应的模式串，如果不存在答案就为。单次查询的时间复杂度为。

第一次出现的位置¶

给定一个文本串，多组查询。每次查询字符串在字符串中第一次出现的位置（的开头位置）。

我们再构造一个后缀自动机。我们对自动机中的所有状态预处理位置。即，对每个状态我们想要找到第一次出现这个状态的末端的位置。换句话说，我们希望先找到每个集合中的最小的元素（显然我们不能显式地维护所有集合）。

为了维护这些位置，我们将原函数扩展为 sa_extend() 。当我们创建新状态时，我们令：

；当我们将顶点复制到时，我们令：

（因为值的唯一其它选项肯定太大了）。

那么查询的答案就是，其中为对应字符串的状态。单次查询只需要的时间。

所有出现的位置¶

问题同上，这一次需要查询文本串中模式串出现的所有位置。

我们还是为文本串构造后缀自动机。与上一个问题相似地，我们为所有状态计算位置。

如果为对应于模式串的状态，显然为答案的一部分。需要查找的其它位置怎么办？我们使用了含有字符串的自动机，我们还需要将哪些状态纳入自动机呢？所有对应于以为后缀的字符串的状态。换句话说我们要找到所有可以通过后缀链接到达状态的状态。

因此为了解决这个问题，我们需要为每一个状态保存一个指向它的后缀引用列表。查询的答案就包含了对于每个我们能从状态只使用后缀引用进行 DFS 或 BFS 的所有状态的值。

这种变通方案的时间复杂度为，因为我们不会重复访问一个状态（因为对于仅有一个后缀链接指向一个状态，所以不存在两条不同的路径指向同一状态）。

我们只需要考虑两个可能有相同值的不同状态。如果一个状态是由另一个复制而来的，则这种情况会发生。然而，这并不会对复杂度分析造成影响，因为每个状态至多被复制一次。

此外，如果我们不从被复制的节点输出位置，我们也可以去除重复的位置。事实上对于一个状态，如果经过被复制状态可以到达，则经过原状态也可以到达。因此，如果我们给每个状态记录标记 is_clone ，我们就可以简单地忽略掉被复制的状态，只输出其它所有状态的的值。

以下是实现的框架：

struct state {
  ... bool is_clone;
  int first_pos;
  vector<int> inv_link;
};

// 在构造后缀自动机后
for (int v = 1; v < sz; v++) {
  st[st[v].link].inv_link.push_back(v);
}

// 输出所有出现位置
void output_all_occurrences(int v, int P_length) {
  if (!st[v].is_clone) cout << st[v].first_pos - P_length + 1 << endl;
  for (int u : st[v].inv_link) output_all_occurrences(u, P_length);
}

最短的没有出现的字符串¶

给定一个字符串和一个特定的字符集，我们要找一个长度最短的没有在中出现过的字符串。

我们在字符串的后缀自动机上做动态规划。

令为节点的答案，即，我们已经处理完了子串的一部分，当前在状态，想找到不连续的转移需要添加的最小字符数量。计算非常简单。如果不存在使用字符集中至少一个字符的转移，则。否则添加一个字符是不够的，我们需要求出所有转移中的最小值：

问题的答案就是，字符串可以通过计算过的数组逆推回去。

两个字符串的最长公共子串¶

给定两个字符串和，求出最长公共子串，公共子串定义为在和中都作为子串出现过的字符串。

我们为字符串构造后缀自动机。

我们现在处理字符串，对于每一个前缀都在中寻找这个前缀的最长后缀。换句话说，对于每个字符串中的位置，我们想要找到这个位置结束的和的最长公共子串的长度。

为了达到这一目的，我们使用两个变量， 当前状态 和 当前长度 。这两个变量描述当前匹配的部分：它的长度和它们对应的状态。

一开始且，即，匹配为空串。

现在我们来描述如何添加一个字符并为其重新计算答案：

如果存在一个从到字符的转移，我们只需要转移并让自增一。
如果不存在这样的转移，我们需要缩短当前匹配的部分，这意味着我们需要按照以下后缀链接进行转移：

与此同时，需要缩短当前长度。显然我们需要将赋值为，因为经过这个后缀链接后我们到达的状态所对应的最长字符串是一个子串。

如果仍然没有使用这一字符的转移，我们继续重复经过后缀链接并减小，直到我们找到一个转移或到达虚拟状态（这意味着字符根本没有在中出现过，所以我们设置）。

问题的答案就是所有的最大值。

这一部分的时间复杂度为，因为每次移动我们要么可以使增加一，要么可以在后缀链接间移动几次，每次都减小的值。

代码实现：

string lcs(string S, string T) {
  sa_init();
  for (int i = 0; i < S.size(); i++) sa_extend(S[i]);

  int v = 0, l = 0, best = 0, bestpos = 0;
  for (int i = 0; i < T.size(); i++) {
    while (v && !st[v].next.count(T[i])) {
      v = st[v].link;
      l = st[v].length;
    }
    if (st[v].next.count(T[i])) {
      v = st[v].next[T[i]];
      l++;
    }
    if (l > best) {
      best = l;
      bestpos = i;
    }
  }
  return t.substr(bestpos - best + 1, best);
}

多个字符串间的最长公共子串¶

给定个字符串。我们需要找到它们的最长公共子串，即作为子串出现在每个字符串中的字符串。

我们将所有的子串连接成一个较长的字符串，以特殊字符分开每个字符串（一个字符对应一个字符串）：

然后为字符串构造后缀自动机。

现在我们需要在自动机中找到存在于所有字符串中的一个字符串，这可以通过使用添加的特殊字符完成。注意如果包含了一个子串，则后缀自动机中存在一条从包含字符的子串而不包含以其它字符开始的路径。

因此我们需要计算可达性，它告诉我们对于自动机中的每个状态和每个字符是否存在这样的一条路径。这可以容易地通过 DFS 或 BFS 与动态规划计算。在此之后，问题的答案就是状态的字符串中存在所有特殊字符的路径。

例题¶

SPOJ #7258 SUBLEX
HihoCoder #1441 : 后缀自动机一·基本概念

后缀自动机 (SAM)

后缀自动机的定义¶

子串的性质¶

构造后缀自动机的实例¶

在线性时间内构造后缀自动机¶

结束位置¶

后缀链接¶

小结¶

算法¶

正确性证明¶

对操作次数为线性的证明¶

实现¶

更多的性质¶

状态数¶

转移数¶

应用¶

检查字符串是否出现¶

不同子串个数¶

所有不同子串的总长度¶

字典序第大子串¶

最小循环移位¶

出现次数¶

第一次出现的位置¶

所有出现的位置¶

最短的没有出现的字符串¶

两个字符串的最长公共子串¶

多个字符串间的最长公共子串¶

例题¶

相关资料¶

评论

后缀自动机 (SAM)

后缀自动机的定义¶

子串的性质¶

构造后缀自动机的实例¶

在线性时间内构造后缀自动机¶

结束位置endpos¶

后缀链接link¶

小结¶

算法¶

正确性证明¶

对操作次数为线性的证明¶

实现¶

更多的性质¶

状态数¶

转移数¶

应用¶

检查字符串是否出现¶

不同子串个数¶

所有不同子串的总长度¶

字典序第k大子串¶

最小循环移位¶

出现次数¶

第一次出现的位置¶

所有出现的位置¶

最短的没有出现的字符串¶

两个字符串的最长公共子串¶

多个字符串间的最长公共子串¶

例题¶

相关资料¶

评论

结束位置¶

后缀链接¶

字典序第大子串¶