SAM练习题

常用结论：

1. 字符串border排序后可以分成O(log|s|)段，每段是一个等差数列。
2. 后缀树的 $ parent $ 树是原串反串的后缀树。

代码：

const int N = 100010;
struct SAM {
	int ch[26][N + N], fa[N + N], len[N + N], lst, sz, f[N + N];
	int sa[N + N], tex[N + N];
	void init() {
		for(int i = 1; i <= sz; i++) {
			fa[i] = len[i] = 0; for(int j = 0;j < 26; j++) ch[j][i] = 0;
		}
		lst = sz = 1;
	}
	void ins(int c) {
		int p = lst, np = ++sz; lst = np, len[np] = len[p] + 1;
		for(; !ch[c][p]; p = fa[p]) ch[c][p] = np;
		if(!p) fa[np] = 1;
		else {
			int q = ch[c][p]; if(len[q] == len[p] + 1) fa[np] = q;
			else {
				int nq = ++sz;
				len[nq] = len[p] + 1, fa[nq] = fa[q], fa[q] = fa[np] = nq;
				for(int i = 0; i < 26; i++) ch[i][nq] = ch[i][q];
				for(; ch[c][p] == q; p = fa[p]) ch[c][p] = nq;
			}
		}
	}
	void Sort() {
		for(int i = 1; i <= sz; i++) ++tex[len[i]];
		for(int i = 1; i <= sz; i++) tex[i] += tex[i-1];
		for(int i = 1; i <= sz; i++) sa[tex[len[i]]--] = i;
		for(int i = sz, u; i; i--) u = sa[i], rt[fa[u]] = merge(rt[fa[u]], rt[u]);
	}
};

例题：

模板 后缀自动机

模板 后缀自动机
题意：给定一个只包含小写字母的字符串 $ S $ , 请你求出 $ S $ 的所有出现次数不为 $ 1 $ 的子串的出现次数乘上该子串长度的最大值。
做法：建后缀自动机，定义每个节点 $ sz[i] = 1 $，将所有串的拓扑序得到，从后往前枚举，每次 $ sz[fa[u]] += sz[u], ans = Max(ans, len[u] * sz[u]) $。

---

TJOI2015 弦论

TJOI2015 弦论
题意：对于一个给定的长度为 $ n $ 的字符串,求出它的第k小子串是什么。
做法：建后缀自动机，定义每个节点 $ sz[i] = 1 $，将所有串的拓扑序得到，从后往前枚举，每次 $ sz[fa[u]] += sz[u] (t = 1), sz[u] = 1 (t = 0) $，再从前往后，每次 $ for (j; 0; 26) sum[u] += sum[ch[u][j]] $ ，从根节点按字典序 $ dfs $ ，得到答案。

---

AHOI2013 差异

AHOI2013 差异
题意请看链接。
做法：求两个后缀的最长公共前缀，显然就是两个后缀的节点在 $ Parent $ 树上的 $ LCA $ 。以 $ p $ 为儿子的边的边权为 $ len[p]-len[fa[p]] $ ，我们考虑一条边对答案的贡献，显然就是有 $ sz[p] \times (n - sz[p] ) $ 条路径经过这条边，乘上边权加入答案即可。

---

USACO17DEC Standing Out from the Herd

USACO17DEC Standing Out from the Herd
题意见链接。
做法：建出广义后缀自动机，再将每一个字符串每一个位置插入后缀自动机（节点权值加一），最后后缀自动机节点权值为一的点为独特点，它的贡献为它在 $ parent $ 树上的深度减去它的父亲在 $ parent $ 树上的深度。

---

SCOI2012 喵星球上的点名

SCOI2012 喵星球上的点名
建出广义后缀自动机，建出 $ parent $ 树，显然一个串的贡献为它在 $ parent $ 树的子树大小。然后可以莫队处理。

---

LCS - Longest Common Substring

LCS - Longest Common Substring
题意：给定两个字符串，求出它们的最长公共子串。
做法：给其中一个串建后缀自动机，另一个串分别与其匹配，再过程中对 $ len[u] $ 取 $ Max $ 即可。

---

ZJOI2015 诸神眷顾的幻想乡

ZJOI2015 诸神眷顾的幻想乡
题意：给出一个字母树，任何一条从叶子开始的有向路径为一个字符串，询问不同的字符串个数。
做法：将每个叶子节点定位根 $ dfs $ ，建广义后缀自动机，对于每个节点，对答案的贡献为 $ len[u] - len[fa[u]] $。

---

CF235C Cyclical Quest

CF235C Cyclical Quest
题意：给一个主串和多个询问串，求询问串的所有样子不同的周期同构出现次数和。
做法：给主串建后缀自动机，拓扑排序计算主串的某个子串出现次数。对于每个询问，将询问串倍长（最后一个串不复制），然后在自动机上跑，若匹配长度大于等于原询问串长度且是为访问过的状态，则答案加上该子串出现次数。

---

LCS2 - Longest Common Substring II

LCS2 - Longest Common Substring II
题意：给定一些字符串，求出它们的最长公共子串。
做法：给其中一个串建后缀自动机，其他串分别与其匹配，记录自动机上每个节点能匹配的最长长度，取 $ Max $ 即可。

---

SDOI2016 生成魔咒

SDOI2016 生成魔咒
题意：每次再字符串末尾新加入一个字符（数字），并求当前字符串中本质不同的字串的的个数。
做法：考虑建 $ SAM $ 的过程是在线的，每次增加的贡献为 $len[np] - len[fa[np]]$。

---

NOI2015 品酒大会

NOI2015 品酒大会
强力的HACK数据

题意： $ \forall i \in [0, n) $ ，求有多少对后缀满足 $ len(lcp) \geq i $ ， 并求出两个后缀的权值乘积的最大值。
做法：将串倒着建后缀自动机，使 $ lcs $ 变成 $ lcp $ ，然后构造 $ parent $ 树，便可以从孩子里得到信息，计数问题转移显然。由于数据存在负数，所以可能负负得正得到最优解。记录一个节点子树中最大值、最小值、次大值、次小值，然后转移。当然还有许多细节（交UOJ就知道了）。

---

「雅礼集训 2017 Day7」事情的相似度

「雅礼集训 2017 Day7」事情的相似度
题意：给你一个长度为 $ n $ 的01串，$ m $ 次询问，每次询问给出 $ l $ 、$ r $ ，求从 $ [l,r] $ 中选出两个不同的前缀的最长公共后缀长度的最大值。 $ n,m \leq 10^5 $
做法：建后缀自动机，那么任意两个前缀的最长公共后缀即为parent树上的LCA深度。将询问离线，按右端点排序，每次加入一个前缀，就将他们在parent树上到根节点的路径打上他们的标记。access时，若遇到了以前打的标记，则该节点为旧标记与新标记的lca。将贡献计入树状数组（维护前缀最大值）并将旧覆盖。

---

「雅礼集训 2017 Day1」字符串

「雅礼集训 2017 Day1」字符串
题意：先给你一个模式串，然后再给出若干个询问区间（即接下来询问的子串位置）。接着有q次询问，给出若干个相同长度的字符串以及l, r，让你分别求出第l个询问区间到第r个询问区间在模式串中出现次数之和（下标从0开始计算）。
做法：
显然的暴力做法是将模式串建后缀自动机后询问无脑匹配。
然后这道题很奇怪的一点是询问次数乘上询问串长度不大于100000。
假如询问串长度比较小，就用一个二维动态数组存储询问串下标确定时有哪些询问区间编号。每次询问枚举询问串左右下标在自动机上跑判断是否合法，然后在用lower_bound找出用到的询问区间个数，然后询问串长度不大于 $ \sqrt {100000} $ 的就过了，实测至少60分。
假如询问很少，我们就对每个询问串，在自动机上跑，预处理每个节点在parent树上的位置及能往前匹配的最长长度，然后暴力枚举用到的询问区间，先判断合法，然后在倍增到这个询问区间的长度，然后就过了。
话说这道题可以拆成两部分的性质真的不太明显。

---