SAM

关于后缀自动机整个算法，在这了就不多说了，感觉别人写的都很好QAQ

可以去看看参考资料里的几篇文章，感觉学过OI的应该都能看懂。。

在这里我就写一下自己的理解和一些性质和应用

我的模版

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
32
33
34
35
36
37
38
39
40
41
42
43
44

void extend(int c)
{
	knum++;
	int u = last;
	int v = knum;
	last = knum;
	len[v] = len[u] + 1;
	for (; u && ! to[u][c]; u = pre[u])
	{
		to[u][c] = v;
	}
	if (! u)
	{
		pre[v] = root;
		return;
	}
	int w = to[u][c];
	if (len[u] + 1 == len[w])
	{
		pre[v] = w;
		return;
	}
	knum++;
	int neww = knum;
	pre[neww] = pre[w];
	len[neww] = len[u] + 1;
	for (int i = 0; i < 26; i++)
	{
		to[neww][i] = to[w][i];
	}
	pre[w] = pre[v] = neww;
	for (; u && to[u][c] == w; u = pre[u])
	{
		to[u][kkc] = neww;
	}
}

int main()
{
	//init
	last = 1;
	knum = 1;
	root = 1;
}

时间复杂度

状态数

状态数是$O(n)$的，这十分显然。

每个状态按照pre边连接可以变成一棵树。

父子节点集合关系是包含的

兄弟节点集合关系是无交的

所以脑补一下，就可以发现状态个数最多就是二叉树的时候，也就只有$2n-1$。。。

转移数

首先，一个十分显然的结论是，转移数最多为$O(\Sigma * n)$，其中$\Sigma$表示字符集大小

有一个更加紧的上限：

$$3n-4\; (对于n\geq 3)$$

然后，考虑以下的事实：

初始节点开始的最长的转移路径树

节点数为$2n-1$，那么边数即为$2n-2$

考虑不在这棵树中的转移$u\to v$，字符为$y$

那么初始节点到$u$的字典序最大字符串（最小应该也行，只要保证唯一）$x$，以及$v$到任意一个终止节点的最长字符串（同样也可以是最小）$z$。

$x+y+z$即为原串的一个后缀，后缀只有$n-1$个，（原串这个后缀肯定在刚开始的树上）。

因此转移数的上限即为$3n-4$

能达到上限的字符串

$$abb \dots bc$$

修改to的次数

从上面的模版可以看出，现在除了

1
2
3
4

for (; u && to[u][c] == w; u = pre[u])
{
    to[u][kkc] = neww;
}

这一段之外时间复杂度就是$O(n)$

那么，这一段的总共的时间复杂度是多少呢？

定义$minlen(u)$表示为能走到$u$的所有字符串的最小长度

显然$minlen$有一个性质：

$$minlen(u)>minlen(pre[u])>minlen(pre[pre[u]])\cdots > minlen(root) \quad (*)$$

那么考虑$minlen(pre[last])$这个东西

如果执行到了这个for循环，那么$pre[last]$就变成了$neww$

可以发现这个for循环如果循环了$k$次

那么$minlen(neww)\leq minlen(lastu)+1$，其中$lastu$是for循环枚举的最后的$u$

通过$(*)$可以知道$minlen(lastu)\leq minlen(pre[last])-k$

那么$minlen(pre[neww])\leq minlen(pre[last])-k+1$

其中$+1$最多加$n$次，$minlen(pre[last])$的初值为$0$

从而for循环执行的次数是$O(n)$的

总结

从上面三部分可知，构建后缀自动机的的时间复杂度为$O(n)$

如果有不懂的欢迎打扰

如果有哪位大佬能想出更好的证明方法的话，请务必告诉我QAQ

一些性质及应用

• 后缀自动机每个节点的状态为：后面还要输入哪些串就是一个后缀

• 对于后缀自动机中每个节点所表示的字符串（起点到这个节点的所有字符串），是在原串中出现位置一模一样的所有字符串。按照长度排序后，是长度依次减一并且是前一个的后缀。比如：$abcac, bcac, cac$

• 一个节点沿着pre一直走到起始节点的所有节点所表示的所有字符串，正好是最长的字符串的所有后缀

本质不同的字串个数

答案显然是$\sum_u len[u] - len[pre[u]]$

字符串循环移位的最小表示

求$S$的循环移位的最小表示

将$S+S$建一个后缀自动机

然后从起始节点开始贪心每次选最小的出边，选择$|S|$次后得到的字符串就是最小表示

求$right$集合

可以在每次extend之后令size[last] = 1，然后按照pre边可以求出每个状态$right$集合的大小

如果只是想单纯地输出每个状态的集合的话，可以直接沿着pre边的反向边求出$right$集合。因为前面也已经说过，走到的状态数最多只有$2|right|-1$个

当然也可以利用线段树合并搞出每个状态具体的$right$集合，这样就会多一个$log$

用拓扑排序的写法写起来比较简单，也可以用DFS

求两个串的最长公共子串

求$S$和$T$的最长公共子串

可以先对$S$建一个后缀自动机

然后拿$T$在自动机上跑，如果有转移则转，没有转移就沿着pre向上跳（话说这不是自动机的基本操作吗。。。）

每次转移后拿len更新答案

推广：广义后缀自动机

说是广义，其实就是建多个串$S_i$的后缀自动机。。。

那么应该怎么建呢？

一种十分简单粗暴的方法就是将$S_1+’ #’+S_2+’ #’+\cdots +’ #’+S_k$建后缀自动机

还有一种方法，就是将原来的模版改成这样：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

void extend(int c)
{
	int u = last;
	if (to[u][c])
	{
		int w = to[u][c];
		if (len[u] + 1 == len[w])
		{
			return w;
		}
		knum++;
		int neww = knum;
		pre[neww] = pre[w];
		for (int i = 0; i < s; i++)
		{
			to[neww][i] = to[w][i];
		}
		len[neww] = len[u] + 1;
		pre[w] = neww;
		for (; u && to[u][c] == w; u = pre[u])
		{
			to[u][c] = neww;
		}
		return neww;
	}
	knum++;
	int v = knum;
	last = knum;
	len[v] = len[u] + 1;
	for (; u && ! to[u][c]; u = pre[u])
	{
		to[u][c] = v;
	}
	if (! u)
	{
		pre[v] = root;
		return;
	}
	int w = to[u][c];
	if (len[u] + 1 == len[w])
	{
		pre[v] = w;
		return;
	}
	knum++;
	int neww = knum;
	pre[neww] = pre[w];
	len[neww] = len[u] + 1;
	for (int i = 0; i < 26; i++)
	{
		to[neww][i] = to[w][i];
	}
	pre[w] = pre[v] = neww;
	for (; u && to[u][c] == w; u = pre[u])
	{
		to[u][kkc] = neww;
	}
}
int main()
{
	//init
	last = 1;
	knum = 1;
	root = 1;
	for (int i ; ;)
	{
		//add Si
		last = root;
	}
}

每次添加完一个字符串后将last赋为root就行了

参考资料

1. http://nirobc.com/20181224.pdf

2. https://oi-wiki.org/string/sam/

3. https://blog.csdn.net/qq_35649707/article/details/66473069