垂死病中惊坐起, 笑闻学弟切SAM

是时候补一篇学习笔记了

为啥每次我打后缀自动机都出来孩子战斗机啊

定义

// 基本上是自己瞎捷豹编的

s: SAM的起点, 一切转移从这里开始…

endpos[(string) x]: 字符串x在原串中出现位置(取x结尾的下标)的集合

终点: 所有endpos包含n的节点都是终点(感谢yt姐姐告诉我终点有很多个qwq)

节点: 自动机中的点, 一个节点包含着一类endpos相同(必须 完 全 一 致 )的子串

maxlen[x]minlen[x]: 代表节点x中包含的长度最长的子串和长度最短的子串(有的时候也省略为起长度)

节点后缀: 对于节点x, 节点后缀就是maxlen[x]的所有后缀, 显然这个节点包含的所有的子串属于这个点的节点后缀, 而长度大于minlen[x]的节点后缀就是这个节点所包含的节点

边:

  • trans[x][y]: 在节点x处后一个字符为y时转移到的节点; 如果不能识别, trans[x][y] = NULL
  • suff_link[x]: 指向 [包含 [第一个长度小于minlen[x]的节点后缀] 的节点], 因为minlen沿着suff_link是单调递减的, 所以最后一定会变为空串, 即指向初始节点s
  • suff_path[x]: 从节点x开始, 由suff_link一直向上, 组成的路径, 终点为s(显然suff_path[x]上的节点的endpos都会包含endpos[x])

转移

// 一个大分类讨论…

maxlen为当前串的节点为x, 新加入的字符为y…我们现在需要给所有合法的后缀都在后面加上一个字符y, 因为原串扩充了一位所以肯定要增加一个节点, 先++cntn为敬

I

对于任意节点$j \in \text{suff_path[x]}$, 都有trans[j][y] = NULL

也就是所有的终点(suff_path[x]上所有点的endpos都包含n, 也就是说他们都是终点)即当前串的所有后缀在当前串的子串都不能向y转移, 既然坑上没有萝卜我们就可以直接让suff_path上的节点trans[j][y] = cntn; 最后让suff_link[cntn] = s, 因为之前的串上没有trans[j][y], 终点又变成1个了

II

在沿着suff_path[x]向上跳的时候, 对于trans[j][y] = NULL的点, 同I我们可以直接把他们的trans赋成cntn;

而遇到trans[j][y] != NULLmaxlen[trans[j][y]] = maxlen[j] + 1(为什么放在下面说)的情况时, 我们发现我们没有必要继续向上跳了(上面的点也一定有trans[j][y] != NULL)我们可以直接把这些trans[j][y]作为终点, 让suff_link[x] = trans[j][y]然后就可以直接返回了

III

在沿着suff_path[x]向上跳的时候, trans[j][y] = NULL时处理还是同上

否则trans[j][y] != NULLmaxlen[trans[j][y]] > maxlen[j] + 1: 这个trans[j][y]并不是直接由j转移来的, 所以如果我们把这个点当做一个终点的话, 就会造成非后缀被识别为后缀(因为到达了终点), 所以我们要复制一个新点;

我们新建一个点c, suff_link[c] = suff_link[trans[j][y]], trans[c] = trans[trans[j][y]], maxlen[c] = maxlen[j] + 1, 即我们新建一个节点作为终点, 且是只由j转移来的, 然后后面的就和II是一样的了: suff_link[cntn] = c

然后再做一些处理: 修改suff_link[trans[j][y]] = c(节点ctrans[j][y]的最长公共后缀是最长的); 沿着suff_path[j]向上走, 对于路径上所有通过y转移到trans[j][y]的节点g: trans[g][y] = c(这些节点的后缀都是j的后缀, 加上y后也就是新串的后缀);


是不是也不是很难?

几道例题

后缀自动机二·重复旋律5

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXZ = 26, MAXN = 1000000 + 5;
struct SAM {
    struct node {
        int trans[MAXZ], suff_link, maxlen;
        node (int ml = 0): suff_link(0), maxlen(ml) { memset(trans, 0, sizeof(trans)); }
    } b[MAXN * 2];
    int s, last, cntb;
    void init() { s = last = cntb = 1; }
    int ins(char xc) {
        int y = xc - 'a', dq = ++cntb, dql = last;
        b[dq] = node(b[dql].maxlen + 1);
        for (; dql && !b[dql].trans[y]; dql = b[dql].suff_link)    b[dql].trans[y] = dq;
        if (!dql)    b[dq].suff_link = s;
        else if (b[b[dql].trans[y]].maxlen == b[dql].maxlen + 1)    b[dq].suff_link = b[dql].trans[y];
        else {
            int c = ++cntb, bd = b[dql].trans[y];
            b[c] = node(b[dql].maxlen + 1);
            for (int i = 0; i < MAXZ; i++)    b[c].trans[i] = b[bd].trans[i];
            b[c].suff_link = b[bd].suff_link;
            b[bd].suff_link = b[dq].suff_link = c;
            for (; dql && b[dql].trans[y] == bd; dql = b[dql].suff_link)    b[dql].trans[y] = c;
        }
        return (last = dq);
    }
}refun;
int main() {
    refun.init();
    char srs[MAXN];
    scanf("%s", srs);
    int n = strlen(srs);
    LL ans = 0;
    for (int i = 0; i < n; i++) {
        int last = refun.ins(srs[i]);
        ans += (refun.b[last].maxlen - refun.b[refun.b[last].suff_link].maxlen);
    }
    printf("%lld", ans);
    return 0;
}

后缀自动机三·重复旋律6

这题还是挺有意思的

endpos[x]就是所有suff_link[j] == x(这些j被称为$parent$树上x的儿子)的endpos的并(看不懂的去瞅一眼定义…); 如果这个x包含了总串的某个前缀, 这个endpos[x]还要再加上自身的位置(这个位置肯定不会包含在x的儿子中, 因为儿子都比x要长, 不会是原串这个位置的前缀)

然后数组开小了加上手残调了一个多小时…

我不知道我都干了什么…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXZ = 26, MAXN = 1000000 + 5;
struct SAM {
    struct node {
        int  maxlen, suff_link, trans[MAXZ];
        node(int maxlen = 0): maxlen(maxlen), suff_link(0) { memset(trans, 0, sizeof(trans)); }
    } b[MAXN << 1];
    int s, last, cntb;
    void init() { s = last = cntb = 1; }
    int ins(char xc) {
        int dq = ++cntb, y = xc - 'a', dql = last;
        b[dq] = node(b[last].maxlen + 1);
        for (; dql && !b[dql].trans[y]; dql = b[dql].suff_link)    b[dql].trans[y] = dq;
        if (!dql)    b[dq].suff_link = s;
        else if (b[dql].maxlen + 1 == b[b[dql].trans[y]].maxlen)    b[dq].suff_link = b[dql].trans[y];
        else {
            int c = ++cntb, dqd = b[dql].trans[y];
            b[c] = node(b[dql].maxlen + 1); // 这个地方一不小心打成 b[c] = node(b[last].maxlen + 1); 了...我也不知道我怎么搞的...
            b[c].suff_link = b[dqd].suff_link;
            b[dqd].suff_link = b[dq].suff_link = c;
            for (int i = 0; i < MAXZ; i++)    b[c].trans[i] = b[dqd].trans[i];
            for (; dql && b[dql].trans[y] == dqd; dql = b[dql].suff_link)    b[dql].trans[y] = c;
        }
        return (last = dq);
    }
}refun;
struct edg {
    int to, next;
} b[MAXN << 1];
int g[MAXN << 1], cntb, size[MAXN << 1], ans[MAXN]; 
void adn(int from, int to) {
    b[++cntb].next = g[from];
    b[cntb].to = to;
    g[from] = cntb;
}
int dfs(int dq) {
    for (int i = g[dq]; i; i = b[i].next)    size[dq] += dfs(b[i].to);
    ans[refun.b[dq].maxlen] = max(ans[refun.b[dq].maxlen], size[dq]);
    return size[dq];
}
int main() {
    refun.init();
    int n = 0;
    do {
        char src = getchar();
        if (src < 'a' || src > 'z') break;
        size[refun.ins(src)] = 1, ++n;
    } while (true);
    for (int i = 2; i <= refun.cntb; i++)    adn(refun.b[i].suff_link, i);
    dfs(1);
    for (int i = n - 1; i >= 1; i--)    ans[i] = max(ans[i], ans[i + 1]);
    for (int i = 1; i <= n; i++)    printf("%d\n", ans[i]);
    return 0;
}

后缀自动机四·重复旋律7

这种有多个串的题…如果一个答案只能在一个位置算贡献, 我们就不能对多个串分开来算了, 我们可以把这些串都拼在一起, 然后在中间加上不可见字符作为分割

这样这个题就很简单了…

忘初始化了…身败名裂

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (2000000 + 5)
#define MAXZ (11)
#define Refun (1000000000 + 7)
#define LL long long
using namespace std;
struct SAM {
    struct node {
        int maxlen, suff_link, trans[MAXZ], vsize; 
        LL sum;
        node(int maxlen = 0): maxlen(maxlen), suff_link(0), sum(0), vsize(0) { memset(trans, 0, sizeof(trans)); }
    } b[MAXN << 1];
    int s, last, cntb, du[MAXN];
    bool inq[MAXN << 1];
    void init() { s = last = cntb = 1; }
    void ins(int y) {
        int dq = ++cntb, dql = last;
        b[dq] = node(b[dql].maxlen + 1);
        for (; dql && !b[dql].trans[y]; dql = b[dql].suff_link) b[dql].trans[y] = dq;
        if (!dql) b[dq].suff_link = s;
        else if (b[dql].maxlen + 1 == b[b[dql].trans[y]].maxlen) b[dq].suff_link =b[dql].trans[y];
        else {
            int c = ++cntb, dqd = b[dql].trans[y];
            b[c] = node(b[dql].maxlen + 1);
            b[c].suff_link = b[dqd].suff_link;
            for (int i = 0; i < MAXZ; i++) b[c].trans[i] = b[dqd].trans[i];
            b[dqd].suff_link = b[dq].suff_link = c;
            for (; dql && b[dql].trans[y] == dqd; dql = b[dql].suff_link) b[dql].trans[y] = c;
        }
        last = dq;
    }
    void solve() {
        LL ans = 0;
        for (int i = 1; i <= cntb; i++)
            for (int j = 0; j < MAXZ; j++)
                if (b[i].trans[j])
                    ++du[b[i].trans[j]];
        queue<int> q;
        q.push(1);
        b[1].vsize = 1;
        while (!q.empty()) {
            int dq = q.front();
            ans = (ans + b[dq].sum) % Refun;
            q.pop();
            for (int i = 0; i < MAXZ; i++)
                if (b[dq].trans[i]) {
                    --du[b[dq].trans[i]];
                    if (i != 10) {
                        b[b[dq].trans[i]].vsize += b[dq].vsize;
                        b[b[dq].trans[i]].sum = (b[b[dq].trans[i]].sum + b[dq].sum * 10 + i * b[dq].vsize) % Refun;
                    }
                    if (!du[b[dq].trans[i]])
                        q.push(b[dq].trans[i]);
                }
        }
         printf("%lld", ans);
    }
} refun;
int n;
char s[MAXN];
int main() {
    scanf("%d", &n);
    refun.init();
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        int tn = strlen(s);
        for (int j = 0; j < tn; j++)
            refun.ins(s[j] - '0');
        refun.ins(10);
    }
    refun.solve();
    return 0;
}

后缀自动机五·重复旋律8

咕咕咕

By 准备退役旅游的 Cansult