盒子
盒子
文章目录
  1. 动机
  2. 怎么做
  3. 性质
  4. 代码
  5. 广义后缀自动机
  6. 应用
    1. 查找某个子串位于哪个节点
    2. 最长可重叠重复子串
    3. 最长不可重叠重复子串
    4. 最长可重叠$k$次重复子串
    5. 最长不可重叠$k$次重复子串
    6. 两个字符串的最长公共子串
    7. 多个字符串的最长公共子串
      1. 方法$1$
      2. 方法$2$
      3. 方法$3$
    8. bzoj 3277 & bzoj 3473
    9. bzoj 2780 & spoj 8093
    10. bzoj 1396 & bzoj 2865
    11. bzoj 2555 & spoj 8747
    12. bzoj 5084
  7. 习题集

（广义）后缀自动机

2018.05.04 nekko algorithm  热度 ℃

动机

如何储存一个字符串的所有子串？

怎么做

后缀自动机！

性质

每一个节点都表示一段子串，所有节点表示的子串们都是唯一的

一个节点的失配节点（大概这些版本：$pre,fail,fa$）表示的是当前节点的某些连续的后缀

节点的$right$集合就是所有反向失配边所指向的那些点的$right$集合的并集

$right$集合就是代表的所有子串出现的那些位置的右端点，每一个节点所表示的那些子串的$right$集合相等

新插入的节点（$np$）的$right$集合为当前坐标（$i$）

$len$表示的是当前节点的最长长度，当前节点的子串长度范围是$(len[pre[u]], len[u]]$

$right$集合的大小可以通过$topo$排序求出来，实际上用桶排实现

当然我们也可以知道$right$集合最靠右和最靠左的分别是哪里

如果必须要求出$right$集合的话，可以用$set$实现树上自底向上启发式合并，当然如果需要每个点的$right$集合都需要求出来的话，可以用动态开点线段树维护$right$集合，然后使用线段树的合并尽心更新$pre[p]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
map<int, int> ch[N];
int pre[N], len[N], sz[N], tot = 1, last = 1, tmp[N], bak[N];
char s[N];
int nd(int l) { return len[++ tot] = l, tot; }
void ins(int c) {
    int p, np, q, nq;
    pre[np = last = nd(len[p = last] + 1)] = 1, sz[np] = 1;
    while(p && !ch[p][c]) ch[p][c] = np, p = pre[p];
    if(p) {
        pre[np] = q = ch[p][c];
        if(len[p] + 1 != len[q]) {
            nq = nd(len[p] + 1), pre[nq] = pre[q];
            ch[nq] = ch[q], pre[np] = pre[q] = nq;
            while(p && ch[p][c] == q) ch[p][c] = nq, p = pre[p];
        }
    }
}
void topo() {
    for(int i = 1 ; i <= tot ; ++ i) tmp[len[i]] ++;
    for(int i = 1 ; i <= tot ; ++ i) tmp[i] += tmp[i - 1];
    for(int i = tot ; i ; -- i) bak[tmp[len[i]] --] = i;
    for(int i = tot ; i ; -- i) {
        int p = bak[i];
        sz[pre[p]] += sz[p];
    }
}
void sol() {
    scanf("%s", s + 1);
    for(int i = 1 ; s[i] ; ++ i) ins(s[i]);
    topo();
}

广义后缀自动机

如果有多个字符串呢？

建立广义后缀自动机！

每添加一个字符串之后把$last$设置为$root$就好

$size$表示一个节点是多少个字符串的公共子串，这个暴力更新一下就行（注意这不是$right$集合大小）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
map<int, int> ch[N];
int pre[N], len[N], sz[N], vis[N], bel[N], tot = 1, last = 1;
char s[N];
int nd(int l) { return len[++ tot] = l, tot; }
void ins(int c, int i) {
    int p, np, q, nq;
    pre[np = last = nd(len[p = last] + 1)] = 1;
    sz[np] = 1, vis[np] = i, bel[np] = i;
    while(p && !ch[p][c]) ch[p][c] = np, p = pre[p];
    if(p) {
        pre[np] = q = ch[p][c];
        if(len[p] + 1 != len[q]) {
            nq = nd(len[p] + 1), pre[nq] = pre[q];
            ch[nq] = ch[q], pre[np] = pre[q] = nq;
            vis[nq] = vis[q], sz[nq] = sz[q];
            while(p && ch[p][c] == q) ch[p][c] = nq, p = pre[p];
        }
    }
    while(np && vis[np] != i) vis[np] = i, sz[np] ++, np = pre[np];
}
void sol() {
    scanf("%d", &n);
    for(int i = 1 ; i <= n ; ++ i) {
        scanf("%s", s + 1);
        last = 1;
        for(int j = 1 ; s[j] ; ++ j) ins(s[j], i);
    }
}

应用

查找某个子串位于哪个节点

给定一个字符串，每次查询某个子串在哪个节点

以$[l,r]$表示子串

直接倍增往上跳到$len[]$合适的地方

最长可重叠重复子串

找一个子串，使得至少出现两次，可以重叠，求最长子串长度

显然就是$right$集合大于等于$2$的那些节点的最大的$len$

最长不可重叠重复子串

找一个子串，使得至少出现两次，不可重叠，求最长子串长度

不光要使得$right$集合大于等于$2$，而且还需要考虑最靠右的那个位置和最靠左的那个位置之间的距离

1
if(sz[u] >= 2) ans = max(ans, min(len[u], r[u] - l[u]));

最长可重叠$k$次重复子串

找一个子串，使得至少出现$k$次，可以重叠，求最长子串长度

显然就是$right$集合大于等于$k$的那些节点的最大的$len$

最长不可重叠$k$次重复子串

找一个子串，使得至少出现$k$次，不可重叠，求最长子串长度

由于$right$集合直接求的话时空复杂度会爆炸，不妨先二分一下答案

设当前二分最长子串长度为$x$，那么只需要将 $len[pre[u]] \lt x \le len[u]]$的那些$u$找出来，并分别计算一下它们的$right$集合，然后把这些位置从小到大排序之后扫一遍并贪心的放入选入集合即可（即当前这个位置能放就放，放不了（即会与之前选择的子串重叠）就不放）

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

给定两个字符串，求它们的最长公共子串有多长

对于其中一个字符串建立$sam$，然后拿另外一个在上面匹配，同时更新最长匹配长度

1
2
3
4
5
6
7
8
9
10
11
for(int i = 1, p = 1, l = 0 ; s[i] ; ++ i) {
    int c = s[i];
    if(ch[p][c]) {
        l ++, p = ch[p][c];
    } else {
        while(p && !ch[p][c]) p = pre[p];
        if(p) l = len[p] + 1, p = ch[p][c];
        else l = 0, p = 1;
    }
    ans = max(ans, l);
}

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

方法$1$

对于第一个字符串建立后缀自动机，然后其他的串在上面匹配，将所有的匹配长度取最小值来更新答案

方法$2$

对于除了第一个字符串的其他字符串建立后缀自动机，然后拿第一个字符串在上面匹配，将所有的匹配长度取最小值来更新答案

方法$3$

建立广义后缀自动机，然后拿$size$大小为$n$的节点的$len$更新答案

bzoj 3277 & bzoj 3473

给定 $n$个字符串，询问每个字符串有多少子串（不包括空串）是所有$n$个字符串中至少$k$个字符串的子串？

广义后缀自动机上对于$sz[u] \ge k$的节点，对第$bel[u]$个字符串的答案的贡献是$len[u] - len[pre[u]]$，以及它的所有的祖先节点的贡献的和

bzoj 2780 & spoj 8093

给你一堆模板串，然后每次询问一个字符串在多少个模板串中出现过

在$exsam$上匹配，失配则答案为$0$，否则答案为最后访问的节点的$size$

bzoj 1396 & bzoj 2865

在这个问题中，给定一个字符串$S$，与一个整数$K$，定义$S$的子串$T=S(i, j)$是关于第$K$位的识别子串，满足以下两个条件：

  1. $i \le k \le j$
  2. 子串$T$只在$S$中出现过一次

如果直接对于每一个位置来统计的话，好像不太可做，那么不妨考虑每一个只出现一次的子串对那些点会产生贡献

显然$ | right | = 1 $ 的那些点所代表的子串会对它所相关的一部分子串产生连续下降的长度贡献，以及剩余部分的不变的贡献

于是成了给定一堆折线，求每个点往上第一个碰到的位置

不妨拆开考虑，斜线和平行线显然是两个部分

斜线的斜率都相同，那么就相当于按照截距从大到小排序之后依次区间赋值

平行线同理，只不过成了从高到低进行排序

用线段树可以做到$O(nlogn)$，但这并不是最优的复杂度

若干次区间赋值、之后输出每个点的值有一种$O(n)$ 的做法

将操作翻转过来，然后暴力标记点，同时将相邻有标记的点缩成一个点

显然每个点访问的次数是$O(1)$级别的，所以总时间复杂度$O(n)$

顺便一提，排序可以用桶排实现$O(n)$排序

好像$bzoj 2865$卡内存所以需要用$map$ ，于是时间复杂度成了$O(nlogn)$

bzoj 2555 & spoj 8747

给你一个初始字符串，每次往后添加一个字符或者询问一个一个字符串在该字符串中出现次数

动态维护$ | right | $，可以用LCT维护

据说直接暴力更新可以切掉$bzoj2555$

bzoj 5084

你有一个字符串$S$，一开始为空串，要求支持两种操作

  1. 在$S$后面加入字母$C$
  2. 删除$S$最后一个字母

问每次操作后$S$有多少个两两不同的连续子串

一个比较$naive$的做法就是，记录一下当前添加字符的时候都修改了哪些节点，并存一下它们原先的值，然后操作二就相当于一个回滚操作，可以用栈来实现

但显然会被卡成$O(n^2)$的，比如说$aaaaaaaab$一直在最后删除$b$然后添加$b$

但是数据随机情况下跑得很快，单次修改的都是常数级别个数的节点

其实这道题就是相当于构建一个$trie$，删除相当于往上跳，插入相当于在树上走一条边，然后对于每一个点，用它的父亲节点作为$last$跑后缀自动机就好

习题集

在这里

支持一下
扫一扫，支持nekko
  • 微信扫一扫