后缀自动机笔记

Author Avatar
dozbear 5月 17, 2017
  • 在其它设备中阅读本文章

准备工作

这篇博客是瞎写的，严格来说只是一点补充内容

可能适用于公式恐惧症患者

在阅读这篇博客之前你需要干的事情：

推荐先阅读 Suffix Automaton Tutorial（中文） 、陈立杰营员交流资料（中文） 和（或） Суффиксный автомат（俄文）（最好使用谷歌翻译，如果你不是特别有自信的话

其实这三个中你应该只要读一个

后缀自动机的节点

假设后缀自动机由字符串 构成

后缀自动机的每个节点都代表了字符串 的某个前缀的连续一段后缀（也就是一段子串）

每个节点所代表的某个前缀的连续一段后缀的结束位置的集合（即 ）都是相同的，任何一个本质相同的后缀都只出现在一个节点中

感性的想，出现的次数越多的一段子串就距离起始位置越近， 也就越大

后缀自动机就是 DFA 加上 Suffix Link 构成的，它是后缀自动机一个比较重要的性质

Suffix Link 是什么？有点类似 KMP 的 和AC自动机的

具体来说，假设存在两个节点 和 ，其中 ，那么，而且 代表的前缀的后缀的集合也是接着 的。比如 代表 ，那么接着的 代表的就是

这种情况下， 一定比 小

感性的说，就是如果从 走到 ，就是牺牲一部分长度换得更多的出现位置

注意到这边 ，因为 。如果 ，那么这两个状态是可以合并的。

还有一个性质就是从 顺着 suffix link 一路走到 ，路径上包含的所有后缀的并就是一个完整的前缀的所有后缀

后缀自动机与广义后缀树

如果把一个串反过来做后缀自动机，然后沿着 suffix link 建树，那么它就是一个萌萌哒广义后缀树啦

为什么呢？因为考虑 suffix link 上包含的东西，其实就是少了一段什么的，是不是和后缀树很像啊

后缀自动机的弱智用法？

当 KMP 用

matchlen 是当前匹配长度

int last, tot;                     // last position and total
int trans[N][C], link[N], len[N];  // transitions, suffix link and maxlen

void build(char *s) {
  // implement suffix automaton
}

void match(char *s) {
  int slen = (int)strlen(s);
  int pos = 1, matchlen = 0;
  for (int i = 0; i < slen; i++) {
    int c = s[i] - 'a';

    if (!pos) {
      pos = 1, matchlen = 0;
    } else {
      matchlen = min(len[pos], matchlen) + 1;
      pos = trans[pos][c];
    }
  }
}

当 AC自动机用

int last, tot;                     // last position and total
int trans[N][C], link[N], len[N];  // transitions, suffix link and maxlen

void add(int c) {
  // add one char to last of suffix automaton
}

void build(char *s) {
  // implement suffix automaton
  int slen = (int)strlen(s);
  last = 1;
  for (int i = 0; i < slen; i++) {
    int c = s[i] - 'a';

    if (!trans[last][c] || len[trans[last][c]] != i + 1) {
      add(c);
    } else {
      last = trans[last][c];
    }
  }
}

void massbuild(char *s[], int num) {
  for (int i = 0; i < num; i++) build(s[i]);
}

然后匹配按照刚才发的做就行

构造后缀数组

很烦自己去uoj看吧懒得放了

感觉正常人也不会用到这个吧

如果你真的用到了，那就只能祝您身体健康了，再见

正常一点的用法呢？

CodeForces 710F

现在有三类操作，一共有 个

  • 加入一个字符串 到集合 中
  • 删除集合 中一个字符串
  • 给出一个字符串 ，查询集合 中有多少个串在 中出现过。如果一个串出现多次，那么你也需要记录多次

强制在线

，

这题哈希就可以过，AC自动机二进制分组也可以过

后缀自动机二进制分组也可以过，但是我们考虑更有趣一点的做法

如果现在我们在节点 ，当前串 的已经匹配长度是 ，当前节点 包含的长度为 的后缀的出现次数是

那么我们需要求出

考虑用数据结构维护，可以使用主席树（动态开点线段树）或者 treap 来维护

时间复杂度

BZOJ 2555

懒得写背景了，给你一个字符串 ，要求你支持两个操作

  • 在当前字符串的后面插入一个字符串
  • 询问字符串 在当前字符串中出现了几次？(作为连续子串)

你必须在线支持这些操作。

100 % 的数据字符串最终长度 ，询问次数 ，询问总长度

直接用动态树维护后缀自动机的 suffix link 树

时间复杂度

BZOJ 3998

对于一个给定字符串 和数字 ，求它的第 小子串是什么。 则表示不同位置的相同子串算作一个。 则表示不同位置的相同子串算作多个。

，

在后缀自动机上沿 suffix link 进行 dfs，记录出每个节点的出现次数 ，然后记录每个节点能转移到的节点的出现次数

然后再大力 dfs 一遍就行啦

BZOJ 3238

给定字符串 ，令 表示它从 开始的后缀。求

可以轻松求出，可是怎么求 呢？

我们反向插入 ，那么这个东西成了一个萌萌哒后缀树

然后呢？后缀树上每个节点的所有转移的 lcp 就是这个节点的 辣

大力 dfs 一下即可

POJ 1743

给定字符串 ，在 中寻找两个不重叠的子串 和 ，使得 且 尽可能大。输出这个最大值。

这个题有个不是很难的后缀数组解法，但是我们可以来一发萌萌哒后缀自动机

我们对于每个节点 的结束位置集合 ，记录其中的最大值 和最小值 ，然后用 来更新答案

TO BE CONTINUED

本作品采用 CC BY-NC-SA 4.0 Unported 进行许可
本文链接：https://dozbear.com/suffix-automaton-review/

Powered by Hexo
Theme - Material