后缀自动机

后缀自动机基本描述

后缀自动机：对于一个字符串$S$S，它对应的后缀自动机是一个最小的确定有限状态自动机，接受且仅接受$S$S的后缀。

栗子：对于字符串S = “aabbabd​”，它的后缀自动机：

其中红色状态是终结状态。对于$S$S的后缀，都可以从$S$S状态出发沿着字符标识路径转移，最后到达终结状态。特别的，对于$S$S的子串，最终会走到一个合法状态；若不是$S$S的子串，最后会无路可走。

---

后缀自动机中的状态

首先介绍子串的结束位置集合$endpos$endpos：对于$S$S的一个子串$s$s，$endpos(s)$endpos(s)为$s$s在$S$S中所有出现的结束位置集合。

把$S$S所有子串的$endpos$endpos求出后，相同的$endpos$endpos集合归为一个状态。

栗子：S = “aabbabd”

状态	子串	endpos
S	空串	{0, 1, 2, 3, 4, 5, 6}
1	a	{1, 2, 5}
2	aa	{2}
3	aab	{3}
4	aabb, abb, bb	{4}
5	b	{3, 4, 6}
6	aabba, abba, bba, ba	{5}
7	aabbab, abbab, bbab, bab	{6}
8	ab	{3, 6}
9	aabbabd, abbabd, bbabd, babd, abd, bd, d	{7}

正好对应上图的状态。

设状态为$st$st，$substrings (st)$substrings(st)表示状态$st$st中的所有子串集合，$longest (st)$longest(st)表示$st$st中最长的子串，$shortest (st)$shortest(st)表示$st$st中最短的子串。

一些性质：

1. 对于$S$S的两个子串$s1$s1、$s2$s2，不妨设$len (s1) \le len (s2)$len(s1)≤len(s2)，那么$s1$s1是$s2$s2的后缀当且仅当$endpos (s2) \subseteq endpos (s1)$endpos(s2)⊆endpos(s1)，$s1$s1不是$s2$s2的后缀当且仅当$endpos (s1) \cap endpos (s2) = \varnothing$endpos(s1)∩endpos(s2)=∅。
2. 对于一个状态$st$st，和任意$s \in substrings (st)$s∈substrings(st)，都有$s$s是$longest (st)$longest(st)的后缀。
3. 对于一个状态$st$st，和任意$longest (st)$longest(st)的后缀$s$s，如果$s$s满足$len (shortest (st)) \le len (s) \le len (longest(st))$len(shortest(st))≤len(s)≤len(longest(st))，那么$s \in substrings (st)$s∈substrings(st)。即$substrings (st)$substrings(st)包含$longest (st)$longest(st)的一系列连续后缀。

---

后缀自动机的Suffix Links

$substrings (st)$substrings(st)包含$longest (st)$longest(st)的一系列连续后缀，但是这连续后缀会在某个地方断掉。如$st=7$st=7，后缀到bab时，下一个ab没有出现在$st$st中，因为ab的$endpos$endpos集合大于bab的$endpos$endpos集合，于是被分配到一个新状态。

可以发现一条状态序列$7 - 8 - 5 - S$7−8−5−S，对应$longest(7)$longest(7)即aabbab的后缀依次在7、8、5、S中。用Suffix links连起来，即是上图中的绿色虚线。

一个状态$st$st的Suffix Link连接到$longest (st)$longest(st)中最长的后缀，且其$endpos$endpos集合与$st$st的$endpos$endpos集合不同。因此$len (shortest (st)) = len (longest (slink [st])) + 1$len(shortest(st))=len(longest(slink[st]))+1，其中$slink[st]$slink[st]表示$st$st的Suffix Link。

---

后缀自动机的Transition Function

对于一个状态$st$st，将$st$st遇到的下一个字符集合记作$next (st)$next(st)。$next(st) = \{ S[i+1], i \in endpos (st) \}$next(st)={S[i+1],i∈endpos(st)}

可以发现$substrings (st)$substrings(st)中的子串接上一个字符$c$c后，新的子串仍属于同一个状态。

因此定义转移函数：$trans (st, c) = x, longest (st) + c \in substrings (x)$trans(st,c)=x,longest(st)+c∈substrings(x)

---

线性时间构造后缀自动机

用增量法构造$S$S对应的SAM。假设已经构造好了$S[1…i]$S[1…i]的SAM，这时要添加字符$S[i+1]$S[i+1]，因此新增了$i+1$i+1个后缀$S[1…i+1], S[2…i+1], …, S[i + 1]$S[1…i+1],S[2…i+1],…,S[i+1]，这些后缀从$S[1…i], S[2 … i], …, S[i]$S[1…i],S[2…i],…,S[i]和空串转移过来。设$S[1 … i]$S[1…i]对应的状态是$u$u，这些串对应的状态正好是$u$u到初始状态$S$S的由Suffix Links连接起来路径上的状态。称这条路径上的所有状态集合是suffix-path (u -> S)。

显然$S[1 … i + 1]$S[1…i+1]这个后缀不能被识别，因此至少要增加一个状态$z$z，$z$z至少包含$S[1 … i + 1]$S[1…i+1]这个后缀。

设$trans (st, c)$trans(st,c)为转移函数，$slink (st)$slink(st)为状态$st$st的Suffix Link

分情况讨论：

1. 对于suffix-path (u -> S)的任意状态$v$v，都有$trans (v, S[i + 1]) = NULL$trans(v,S[i+1])=NULL，此时只要令$trans (v, S[i + 1]) = z$trans(v,S[i+1])=z，$slink (st) = S$slink(st)=S即可。

   栗子：

   

2. 存在suffix-path (u -> S)中的状态$v$v，使得$trans (v, S[i + 1]) = x$trans(v,S[i+1])=x。这意味着已经存在某个字符串$s+c$s+c，其中$s$s是$S$S的后缀，且$s+c$s+c已经作为$S$S的子串出现。则$z$z的Suffix Link应连向一个状态$x$x，这个状态中$longest (x) = s + c$longest(x)=s+c，$len (longest (x)) = len (longest (v)) + 1$len(longest(x))=len(longest(v))+1。这时要分两种情况：

   1. $len (longest (x)) = len (longest (v)) + 1$len(longest(x))=len(longest(v))+1

      直接将$z$z的Suffix Link连向$x$x即可。

      栗子：

      

   2. $len (longest (x)) \gt len (longest (v)) + 1$len(longest(x))>len(longest(v))+1

      这时$x$x不只对应长度为$len (longest (v)) + 1$len(longest(v))+1的后缀，只能将$x$x状态拆开。

      新建一个状态$y$y，$len (longest (y)) = len (longest (v)) + 1$len(longest(y))=len(longest(v))+1

      将原先转移指向$x$x的状态中$len (longest (w)) \le len (longest (v)) + 1$len(longest(w))≤len(longest(v))+1的状态$w$w指向$y$y，$len (longest (w)) \gt len (longest (v)) + 1$len(longest(w))>len(longest(v))+1的状态$w$w指向$x$x，并把$y$y的Suffix Link指向原先$x$x的Suffix Link，将$x$x和$z$z的Suffix Link指向$y$y。

      

      栗子：

      

---

后缀自动机模板

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10 ;
int sz, last ;
char s[maxn] ;
struct node {
    int len, link, nxt[26] ;
}st[maxn] ;
void sam_init () {
    st[0].len = 0; st[0].link = -1 ;
    sz ++; last = 0 ;
}
void insert (int c) {
    int cur = sz ++ ;
    st[cur].len = st[last].len + 1 ;
    int p = last ;
    while (p != -1 && !st[p].nxt[c]) {
        st[p].nxt[c] = cur; p = st[p].link ;
    }
    if (p == -1) {
        st[cur].link = 0; last = cur; return ;
    }
    int q = st[p].nxt[c] ;
    if (st[p].len + 1 == st[q].len) {
        st[cur].link = q ;
    } else {
        int clone = sz ++ ;
        st[clone].len = st[p].len + 1 ;
        for (int i = 0; i < 26; i ++) st[clone].nxt[i] = st[q].nxt[i] ;
        st[clone].link = st[q].link ;
        while (p != -1 && st[p].nxt[c] == q) {
            st[p].nxt[c] = clone; p = st[p].link ;
        }
        st[q].link = st[cur].link = clone ;
    }
    last = cur ;
}
int main() {
    scanf("%s", s + 1) ;
    int len = strlen (s + 1) ;
    sam_init () ;
    for (int i = 1; i <= len; i ++) insert (s[i] - 'a') ;
    return 0 ;
}

其中状态$v$v中的$len$len表示$len (longest (v))$len(longest(v))，$link$link为Suffix Link，$nxt$nxt为转移函数。

---

例题

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

题面：hihocoder 1445

**题意：**求一个字符串中不同子串的数量。

**题解：**对于后缀自动机中的两个状态$x$x、$y$y，$substrings (x) \cap substrings (y) = \varnothing$substrings(x)∩substrings(y)=∅。因此即求$\sum _{st} |substrings (st)|$∑st​∣substrings(st)∣。又知道$shortest (st)$shortest(st)到$longest (st)$longest(st)与$substrings (st)$substrings(st)一一对应，$len (shortest (st)) = len (longest (slink [st])) + 1$len(shortest(st))=len(longest(slink[st]))+1，因此最后求$\sum _{st} len (st) - len (link[st]) + 1$∑st​len(st)−len(link[st])+1。建出后缀自动机后暴力求和即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10 ;
int sz, last ;
char s[maxn] ;
struct node {
    int len, link, nxt[26] ;
}st[maxn] ;
void sam_init () {
    st[0].len = 0; st[0].link = -1 ;
    sz ++; last = 0 ;
}
void insert (int c) {
    int cur = sz ++ ;
    st[cur].len = st[last].len + 1 ;
    int p = last ;
    while (p != -1 && !st[p].nxt[c]) {
        st[p].nxt[c] = cur; p = st[p].link ;
    }
    if (p == -1) {
        st[cur].link = 0; last = cur; return ;
    }
    int q = st[p].nxt[c] ;
    if (st[p].len + 1 == st[q].len) {
        st[cur].link = q ;
    } else {
        int clone = sz ++ ;
        st[clone].len = st[p].len + 1 ;
        for (int i = 0; i < 26; i ++) st[clone].nxt[i] = st[q].nxt[i] ;
        st[clone].link = st[q].link ;
        while (p != -1 && st[p].nxt[c] == q) {
            st[p].nxt[c] = clone; p = st[p].link ;
        }
        st[q].link = st[cur].link = clone ;
    }
    last = cur ;
}
int main() {
    scanf("%s", s + 1) ;
    int len = strlen (s + 1) ;
    sam_init () ;
    for (int i = 1; i <= len; i ++) insert (s[i] - 'a') ;
    long long ans = 0 ;
    for (int i = 1; i < sz; i ++) ans += st[i].len - st[st[i].link].len ;
    cout << ans << endl ;
    return 0 ;
}

---

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

题面：hihocoder 1449

**题意：**给定字符串$S$S，求对于所有的$1 \le k \le len (S)$1≤k≤len(S)，长度为$k$k的出现次数最多的子串的出现次数。

**题解：**后缀自动机中状态$st$st的$endpos$endpos集合的大小即为$substrings (st)$substrings(st)的出现次数。考虑如何算出每个状态的$endpos$endpos集合大小。

先构建后缀自动机：以S = "aabbabd"为例

不考虑转移函数，只考虑Suffix Links。并且，如果一个状态能接受$S$S的前缀，将该状态标为绿色。

状态	子串	endpos
S	空串	{0, 1, 2, 3, 4, 5, 6}
1	a	{1, 2, 5}
2	aa	{2}
3	aab	{3}
4	aabb, abb, bb	{4}
5	b	{3, 4, 6}
6	aabba, abba, bba, ba	{5}
7	aabbab, abbab, bbab, bab	{6}
8	ab	{3, 6}
9	aabbabd, abbabd, bbabd, babd, abd, bd, d	{7}

Suffix Links把后缀自动机中的状态连成了一棵树，且祖孙之间的$endpos$endpos有包含关系，非祖孙之间交为空集。

从两个例子来看这个问题：

1. $endpos (8) = endpos (3) \cup endpos (7)$endpos(8)=endpos(3)∪endpos(7)，$|endpos (8)| = |endpos (3)| + |endpos (7)|$∣endpos(8)∣=∣endpos(3)∣+∣endpos(7)∣
2. $endpos (1) = endpos (2) \cup endpos (6) \cup \{1\}$endpos(1)=endpos(2)∪endpos(6)∪{1}

当一个状态为绿色节点即它能接受$S$S的一个前缀时，它的$endpos$endpos集合大小比它的儿子的集合大小和大1。

即如果一个状态$st$st包含$S$S的一个前缀$S[1 … l]$S[1…l]，那么一定有$l \in endpos (st)$l∈endpos(st)，并且$l$l不能继承自$st$st的儿子。这时需要+1。

如何标记绿色状态：构造后缀自动机时，每次新建的$z$z节点一定是绿色状态，因为对应$S[1 … i +1]$S[1…i+1]这个前缀；复制出的状态$y$y一定不是绿色状态。

求出每个状态的$endpos$endpos集合大小后，因为最后的答案一定关于$k$k递减，因此每次只需要更新$len (longest (st))$len(longest(st))处的值，并从后往前更新一遍。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10 ;
int sz, last ;
struct node {
    int len, link, nxt[26] ;
}st[maxn] ;
char s[maxn] ;
int head[maxn], to[maxn], nxt[maxn], tot = 1 ;
int ans[maxn], f[maxn] ;
bool flag[maxn] ;
void addEdge (int u, int v) {
    to[++ tot] = v; nxt[tot] = head[u]; head[u] = tot ;
}
void sam_init () {
    st[0].len = 0; st[0].link = -1 ;
    sz ++; last = 0 ;
}
void insert (int c) {
    int cur = sz ++; flag[cur] = 1 ;
    st[cur].len = st[last].len + 1 ;
    int p = last ;
    while (p != -1 && !st[p].nxt[c]) {
        st[p].nxt[c] = cur; p = st[p].link ;
    }
    if (p == -1) {
        st[cur].link = 0; last = cur; return ;
    }
    int q = st[p].nxt[c] ;
    if (st[p].len + 1 == st[q].len) {
        st[cur].link = q ;
    } else {
        int clone = sz ++ ;
        st[clone].len = st[p].len + 1 ;
        for (int i = 0; i < 26; i ++) st[clone].nxt[i] = st[q].nxt[i] ;
        st[clone].link = st[q].link ;
        while (p != -1 && st[p].nxt[c] == q) {
            st[p].nxt[c] = clone; p = st[p].link ;
        }
        st[q].link = st[cur].link = clone ;
    }
    last = cur ;
}
int dfs (int v) {
    if (f[v]) return f[v] ;
    int res = 0 ;
    for (int i = head[v]; i; i = nxt[i])
        res += dfs (to[i]) ;
    return f[v] = res + flag[v] ;
}
int main() {
    scanf("%s", s + 1) ;
    int len = strlen (s + 1) ;
    sam_init () ;
    for (int i = 1; i <= len; i ++) insert (s[i] - 'a') ;
    //for (int i = 0; i < sz; i ++) printf("node %d: len:%d link:%d a->%d b->%d\n", i, st[i].len, st[i].link, st[i].nxt[0], st[i].nxt[1]) ;
    for (int i = 1; i < sz; i ++) addEdge (st[i].link, i) ;
    dfs (0) ;
    for (int i = 1; i < sz; i ++) ans[st[i].len] = max (ans[st[i].len], f[i]) ;
    for (int i = len - 1; i >= 1; i --) ans[i] = max (ans[i], ans[i + 1]) ;
    for (int i = 1; i <= len; i ++) printf("%d\n", ans[i]) ;
    return 0 ;
}

---

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

题面：hihocoder 1457

**题意：**给定$n$n个数字串，求每个串中所有不同的数字子串在十进制下的总和。

**题解：**将$n$n个数字串连在一起，中间用":"隔开，构建猴嘴自动机。设$sum (st)$sum(st)为状态$st$st中的子串和。

$sum (st) = \sum _{trans[x][c] = st} sum[x] * 10 + c * cnt (x)$sum(st)=∑trans[x][c]=st​sum[x]∗10+c∗cnt(x)

其中$cnt(x)$cnt(x)表示状态$x$x中不含":"的子串个数，恰好等于从初始状态$S$S到状态$x$x所有的非冒号边的数量。

按照拓扑排序转移即可。注意拓扑排序前度数不能将只有经过冒号边才能到达的边计算进去。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int maxn = 4e6 + 10, mod = 1e9 + 7 ;
int sz, last ;
struct node {
    int len, link, nxt[11] ;
}st[maxn] ;
char s[maxn] ;
int deg[maxn], cnt[maxn] ;
ll f[maxn] ;
bool vis[maxn] ;
void sam_init () {
    st[0].len = 0; st[0].link = -1 ;
    sz ++; last = 0 ;
}
void insert (int c) {
    int cur = sz ++ ;
    st[cur].len = st[last].len + 1 ;
    int p = last ;
    while (p != -1 && !st[p].nxt[c]) {
        st[p].nxt[c] = cur; p = st[p].link ;
    }
    if (p == -1) {
        st[cur].link = 0; last = cur; return ;
    }
    int q = st[p].nxt[c] ;
    if (st[p].len + 1 == st[q].len) {
        st[cur].link = q ;
    } else {
        int clone = sz ++ ;
        st[clone].len = st[p].len + 1 ;
        for (int i = 0; i < 11; i ++) st[clone].nxt[i] = st[q].nxt[i] ;
        st[clone].link = st[q].link ;
        while (p != -1 && st[p].nxt[c] == q) {
            st[p].nxt[c] = clone; p = st[p].link ;
        }
        st[cur].link = st[q].link = clone ;
    }
    last = cur ;
}
void bfs () {
    queue<int> que ;
    que.push (0); vis[0] = 1 ;
    while (!que.empty()) {
        int v = que.front(); que.pop() ;
        for (int i = 0; i < 10; i ++) {
            int to = st[v].nxt[i] ;
            if (!to) continue ;
            if (!vis[to]) que.push (to) ;
            deg[to] ++; vis[to] = 1 ;
        }
    }
}
void topsort () {
    queue<int> que ;
    que.push (0); cnt[0] = 1 ;
    while (!que.empty()) {
        int v = que.front(); que.pop() ;
        for (int i = 0; i < 10; i ++) {
            int to = st[v].nxt[i] ;
            if (!to) continue ;
            if (-- deg[to] == 0) que.push (to) ;
            cnt[to] += cnt[v] ;
            f[to] = (f[to] + f[v] * 10 + cnt[v] * i) % mod ;
        }
    }
}
int main() {
    int n ;
    scanf("%d", &n) ;
    sam_init () ;
    for (int i = 1; i <= n; i ++) {
        scanf("%s", s + 1) ;
        int len = strlen (s + 1) ;
        for (int j = 1; j <= len; j ++) insert (s[j] - '0') ;
        if (i != n) insert (10) ;
    }
    bfs () ;
    topsort () ;
    //for (int i = 1; i < sz; i ++) printf("node:%d cnt:%d f:%lld\n", i, cnt[i], f[i]) ;
    ll ans = 0 ;
    for (int i = 1; i < sz; i ++) ans = (ans + f[i]) % mod ;
    printf("%lld\n", ans) ;
    return 0 ;
}

---

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

题面：hihocoder 1465

**题意：**给定一个大串，多次询问一个小串和大串中的多少子串循环相似。

**题解：**首先对大串建后缀自动机。每个询问的小串将自己的一份复制接在后面。设小串长度为$n$n。$T[n + i] = T[i]$T[n+i]=T[i]

先考虑如何用后缀自动机求$T$T串以第$i$i个字符结尾的与$S$S串的最长公共子串。

设一个二元组$(u, l)$(u,l)表示当前在后缀自动机上的状态$u$u，最长公共子串长度为$l$l。初始化$u=S$u=S，$l = 0$l=0

求出$T[i - 1]$T[i−1]的$(u, l)$(u,l)后，如何求$T[i]$T[i]的$(u, l)$(u,l)：

1. 若存在$trans (u, T[i])$trans(u,T[i])：$u = trans (u, T[i])$u=trans(u,T[i])，$l = l + 1$l=l+1
2. 若$trans (u, T[i])$trans(u,T[i])不存在：沿着suffix-path (u -> S)找到一个状态$v$v满足$trans (v, T[i])$trans(v,T[i])存在，令$u = trans (v, T[i])$u=trans(v,T[i])，$l = len[v] + 1$l=len[v]+1。若$trans (S, T[i])$trans(S,T[i])也不存在，令$u = S$u=S，$l = 0$l=0。

若$l \ge n$l≥n，那么就得到一个循环同构的公共子串$T[i - l + 1 .. i]$T[i−l+1..i]。

还要注意两个特殊情况：

1. $T$T的循环同构串可能会有相同的情况，需要记录状态$(u, l)$(u,l)中的$u$u有没有在$l \ge n$l≥n时到达过。
2. $T[i - l + 1 … i]$T[i−l+1…i]属于状态$u$u。当$l \gt n$l>n时，$T[i - n + 1 … i]$T[i−n+1…i]可能不属于状态$u$u。因此沿着suffix-path (u -> S)上找离$S$S最近的$v$v使$len (v) \ge n$len(v)≥n，统计$|endpos (v)|$∣endpos(v)∣。找到后令$u = v$u=v。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10 ;
int sz, last ;
struct node {
    int len, link, nxt[26] ;
}st[maxn] ;
char s[maxn] ;
int head[maxn], to[maxn], nxt[maxn], tot = 1 ;
int f[maxn] ;
bool vis[maxn], flag[maxn] ;
void sam_init () {
    st[0].len = 0; st[0].link = -1 ;
    sz ++; last = 0 ;
}
void insert (int c) {
    int cur = sz ++; flag[cur] = 1 ;
    st[cur].len = st[last].len + 1 ;
    int p = last ;
    while (p != -1 && !st[p].nxt[c]) {
        st[p].nxt[c] = cur; p = st[p].link ;
    }
    if (p == -1) {
        st[cur].link = 0; last = cur; return ;
    }
    int q = st[p].nxt[c] ;
    if (st[p].len + 1 == st[q].len) {
        st[cur].link = q ;
    } else {
        int clone = sz ++ ;
        st[clone].len = st[p].len + 1 ;
        for (int i = 0; i < 26; i ++) st[clone].nxt[i] = st[q].nxt[i] ;
        st[clone].link = st[q].link ;
        while (p != -1 && st[p].nxt[c] == q) {
            st[p].nxt[c] = clone; p = st[p].link ;
        }
        st[cur].link = st[q].link = clone ;
    }
    last = cur ;
}
void addEdge (int u, int v) {
    to[++ tot] = v; nxt[tot] = head[u]; head[u] = tot ;
}
int dfs (int v) {
    int res = 0 ;
    for (int i = head[v]; i; i = nxt[i])
        res += dfs (to[i]) ;
    return f[v] = res + flag[v] ;
}
int main() {
    sam_init () ;
    scanf("%s", s + 1) ;
    int len = strlen (s + 1) ;
    for (int i = 1; i <= len; i ++) insert (s[i] - 'a') ;
    for (int i = 1; i < sz; i ++) addEdge (st[i].link, i) ;
    dfs (0) ;
    int n ;
    scanf("%d", &n) ;
    for (int i = 1; i <= n; i ++) {
        memset (vis, 0, sizeof vis) ;
        scanf("%s", s + 1) ;
        len = strlen (s + 1) ;
        for (int j = len + 1; j < 2 * len; j ++) s[j] = s[j - len] ;
        int u = 0, l = 0, ans = 0 ;
        for (int j = 1; j <= len * 2 - 1; j ++) {
            while (u != 0 && !st[u].nxt[s[j] - 'a']) {
                u = st[u].link; l = st[u].len ;
            }
            if (st[u].nxt[s[j] - 'a']) {
                u = st[u].nxt[s[j] - 'a'], l ++ ;
            } else {
                u = 0; l = 0 ;
            }
            if (l > len) {
                while (st[st[u].link].len >= len) {
                    u = st[u].link; l = st[u].len ;
                }
            }
            if (l >= len && !vis[u]) {
                vis[u] = 1 ;
                ans += f[u] ;
            }
        }
        printf("%d\n", ans) ;
    }
    return 0 ;
}