后缀自动机SAM
后缀自动机（SAM），可以结合前文的AC自动机一起理解，所谓后缀自动机，就是把一个字符串的所有后缀构造AC自动机，即只匹配其后缀的自动机。但是作为一个字符串的所有后缀，与一般的AC自动机有些不一样的性质，直接构造AC自动机，节点数是 $O(n^2)$，而SAM则对重复的节点合并了，可以让节点数大幅下降到 $O(n)$。
首先我们来直观地看看SAM的图形化，以下是字符串abcac的SAM
graph LR;
linkStyle default interpolate basis
0((0))--a-->1
1--b-->2
2--c-->3
3--a-->4
4--c-->5((5))
0--c-->6(1)
0--b-->2
1--c-->5
6--a-->4
4-.->1
5-.->6
3-.->6
1-.->0
2-.->0
6-.->0
style 0 fill:#f9f
style 5 fill:#f9f
实线方向就是匹配方向，虚线与AC自动机中的失败指针非常像，在SAM里称为link指针。
咱们这里就不从理论上做解释，把构造过程简单模拟一遍，如果你需要证明，那么可以在oiwiki上找到。
SAM构造过程模拟
我们使用字符串abcac作为开始，SAM的构造是一个在线算法，可以一个个字符添加构造。另一点说明，节点编号等于与从根开始出发到该节点的最大深度。
1 插入a
graph LR;
linkStyle default interpolate basis
0((0))--a-->1((1))
1-.->0
style 0 fill:#f9f
style 1 fill:#f9f
2 插入b
graph LR;
linkStyle default interpolate basis
0((0))--a-->1
1--b-->2((2))
0--b-->2
1-.->0
2-.->0
style 0 fill:#f9f
style 2 fill:#f9f
在b添加到主链后，要找2的父节点1的link指针指的节点，命名为p，1. 如果它的下一个不存在字符b，那么再令p = p->link，并再次判断本情况，2. 如果某个p的next存在当前的字符，那就让节点2的link指向p->next[char]节点，3. 如果p已经到达根，那么从根连接一条实边到节点2，同时节点2的link指向根。这里就属于情况3。
3 插入c
graph LR;
linkStyle default interpolate basis
0((0))--a-->1
1--b-->2
2--c-->3
0--b-->2
0--c-->3((3))
1-.->0
2-.->0
3-.->0
style 0 fill:#f9f
style 3 fill:#f9f
4 插入a
这个步骤稍微多一点，先添加到主链，即在1->2->3->4上，得到：
graph LR;
linkStyle default interpolate basis
0((0))--a-->1
1--b-->2
2--c-->3
3--a-->4((4))
0--b-->2
0--c-->3
1-.->0
2-.->0
3-.->0
style 0 fill:#f9f
style 4 fill:#f9f
然后找4的父节点3的link指针指的节点，它的下一个存在字符a，那么指向它，属于前面说的情况2
graph LR;
linkStyle default interpolate basis
0((0))--a-->1
1--b-->2
2--c-->3
3--a-->4((4))
0--b-->2
0--c-->3
1-.->0
2-.->0
3-.->0
4-.->1
style 0 fill:#f9f
style 4 fill:#f9f
5 插入c
此步更为复杂 ，首先还是先加入主链
graph LR;
linkStyle default interpolate basis
0((0))--a-->1
1--b-->2
2--c-->3
3--a-->4
4--c-->5((5))
0--b-->2
0--c-->3
1-.->0
2-.->0
3-.->0
4-.->1
style 0 fill:#f9f
style 5 fill:#f9f
从节点4开始找到节点1，它的next没有当前字符，再找到节点0，节点0的next存在当前字符，即找到节点3，但我们不能直接让节点5的link连接到节点3，因为连接到3的父节点0，它们的的深度不是连续的关系，这时候我们需要做拆点，把原来的节点3复制一个，即next是一样的，link也是一样，然后再让节点0直接连向它（如果不是节点0，那除了它之外，还有它的link节点的next有包含当前字符的，都要指向复制节点），节点3和新插入的节点5的link都指向这个复制节点。
graph LR;
linkStyle default interpolate basis
0((0))--a-->1
1--b-->2
2--c-->3
3--a-->4
4--c-->5((5))
0--c-->6(1)
0--b-->2
1--c-->5
6--a-->4
4-.->1
5-.->6
3-.->6
1-.->0
2-.->0
6-.->0
style 0 fill:#f9f
style 5 fill:#f9f
构造步骤总结
一些说明，节点p有数据next、link、maxlen，next就是匹配的转移表，link连接到p所表示的字符串的最长后缀，可以当成fail指针理解，而maxlen表示从根到节点p的最大深度
- 上一次插入主链的节点命名为
last，新插入节点到主链，命名为cur，当前要插入的字符命名为c，进入步骤2 - 令
p = last看看p->link->next有没有c，没有的话再令p = p->link直到p->link->next有c跳到步骤3。如果p到根仍然找不到，那么令cur->link = root结束 - 令节点
p->next[c]为ch，判断ch->maxlen和p->maxlen+1是不是相等，如果是，令cur->link = p->next[c]，结束。如果不是，到第4步 - 对节点
ch进行分拆操作，先复制，复制节点命名为p2，更新p2的最大深度，再判断如果满足p->next[c] == ch，则令p->next[c] = p2，再令p = p->link重复前一步
对于节点p的minlen，可以通过 p->link->maxlen + 1 得到
模板
struct SAM
{
struct node
{
map<char, int> next;
int link;
int len_max;
node() : link(0), len_max(0) { }
};
vector<node> nodes;
int last;
void init(int size = 1024)
{
nodes.clear();
nodes.reserve(size);
nodes.push_back(node());
last = 0;
nodes[0].link = -1;
}
int size() const
{
return (int)nodes.size();
}
int len_max(int p)
{
return nodes[p].len_max;
}
int len_min(int p)
{
if (p == 0) return 0;
return nodes[nodes[p].link].len_max + 1;
}
void extend(char c)
{
int cur = (int)nodes.size();
nodes.push_back(node());
nodes[cur].len_max = nodes[last].len_max + 1;
int p = last; last = cur;
while (p != -1 && !nodes[p].next.count(c))
{
nodes[p].next[c] = cur;
p = nodes[p].link;
}
if (p == -1)
{
nodes[cur].link = 0;
}
else
{
int ch = nodes[p].next[c];
if (nodes[p].len_max + 1 == nodes[ch].len_max)
{
nodes[cur].link = ch;
}
else // split ch
{
int p2 = (int)nodes.size();
nodes.push_back(nodes[ch]);
nodes[p2].len_max = nodes[p].len_max + 1;
while (p != -1 && nodes[p].next[c] == ch)
{
nodes[p].next[c] = p2;
p = nodes[p].link;
}
nodes[ch].link = nodes[cur].link = p2;
}
}
}
};
SAM应用
1 多模式匹配
给你一个字符串集S以及字符串T，判断T有哪些子串属于S
先对T求SAM，然后对S的每一个字符串走一遍，如果能走到底，那么这个串在T中出现了
2 不同的子串数量
因为对于SAM任何一个节点u，从根到这个节点的路线有 $maxlen(u) - minlen(u) + 1$ 条，而这条路线则表示原字符串的一个子串，且各不相同，所以对所有的节点求和，即 $\sum{(maxlen(u) - minlen(u) + 1)}$
3 字符串的最小表示
这个很简单，对于原串s，长度为k，生成关于s+s串的SAM后，找最小的next节点走k步即可
4 最长公共子串
给出串A和B，对B求SAM，然后把这个SAM仿照KMP给A做匹配，令l表示最大匹配长度，如果next有对应字符就转移，且l++，如果没有则跳转到link所指的节点u，令l = maxlen(u)并再次匹配，l的最大值就是答案。
抱抱熊
一个喜欢折腾和研究算法的大学生