后缀自动机笔记

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

准备工作

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

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

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

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

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

后缀自动机的节点

假设后缀自动机由字符串 \(S\) 构成

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

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

感性的想,出现的次数越多的一段子串就距离起始位置越近,\(|Endpos|\) 也就越大

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

Suffix Link 是什么?有点类似 KMP 的 \(next\) 和AC自动机的 \(fail\)

具体来说,假设存在两个节点 \(u\) 和 \(v\) ,其中 \(link_v = u\),那么\(minlen_v = maxlen_u + 1\),而且 \(v\) 代表的前缀的后缀的集合也是接着 \(u\) 的。比如 \(v\) 代表 \([‘abcdefg’ ,\ ‘bcdefg’ ,\ ‘cdefg’] \),那么接着的 \(u\) 代表的就是 \([‘defg’,\ …]\)

这种情况下,\(|Endpos_v|\) 一定比 \(|Endpos_u|\) 小

感性的说,就是如果从 \(u\) 走到 \(link_u\) ,就是牺牲一部分长度换得更多的出现位置

注意到这边 \(|Endpos_v| \neq |Endpos_u|\),因为 \(Endpos_v \subset Endpos_u\)。如果 \(Endpos_v = Endpos_u\),那么这两个状态是可以合并的。

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

后缀自动机与广义后缀树

如果把一个串反过来做后缀自动机,然后沿着 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

现在有三类操作,一共有 \(m\) 个

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

强制在线

\(m \le 3 \times 10^5\) ,\(\sum |S| \le 3 \times 10^5\)

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

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

如果现在我们在节点 \(u\),当前串 \(S\) 的已经匹配长度是 \(matchlen\),当前节点 \(u\) 包含的长度为 \(i\) 的后缀的出现次数是 \(vis_{u,i}\) ,那么我们需要求出 \(\sum_{i=minlen_u}^{matchlen} vis_{u,i}\)

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

时间复杂度 \(\Theta(n \log n)\)

BZOJ 2555

懒得写背景了,给你一个字符串 \(init\) ,要求你支持两个操作

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

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

100 % 的数据字符串最终长度 \(\le 6 \times 10^5\),询问次数 \(\le 10^4\),询问总长度 \(\le 3 \times 10^6\)

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

时间复杂度 \(\Theta(n \log n)\)

BZOJ 3998

对于一个给定字符串 \(S\) 和数字 \(t\),求它的第 \(K\) 小子串是什么。\(t=0\) 则表示不同位置的相同子串算作一个。\(t=1\) 则表示不同位置的相同子串算作多个。

\(|S| \le 5 \times 10^5\),\(K \le 10^9\)

在后缀自动机上沿 suffix link 进行 dfs,记录出每个节点的出现次数 \(vis_u\),然后记录每个节点能转移到的节点的出现次数 \(sum_u = \sum_{i=0}^{25} sum_{trans_{u,i}}\)

然后再大力 dfs 一遍就行啦

BZOJ 3238

给定字符串 \(S\) ,令 \(T_i\) 表示它从\(i\) 开始的后缀。求

\[\sum_{1 \le i < j \le n} len_{T_i} + len_{T_j} - 2 \times lcp(T_i,T_j) \]

\(|S| \le 5 \times 10^5\)

\( len_{T_i} + len_{T_j} \) 可以轻松求出,可是怎么求 \(lcp(T_i,T_j)\) 呢?

我们反向插入 \(S\),那么这个东西成了一个萌萌哒后缀树

然后呢?后缀树上每个节点的所有转移的 lcp 就是这个节点的 \(len\) 辣

我们大力 dfs 一下

POJ 1743

给定字符串 \(S\),在 \(S\) 中寻找两个不重叠的子串 \(S_1\) 和 \(S_2\),使得 \(S_1 = S_2\) 且 \(|S_1|\) 尽可能大。输出这个最大值。

\(|S| \le 2 \times 10^4\)

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

我们对于每个节点 \(u\) 的结束位置集合 \(Endpos_u\),记录其中的最大值 \(maxpos\) 和最小值 \(minpos\),然后用 \(min( len_u , maxpos-minpos)\) 来更新答案

TO BE CONTINUED

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