本文共 2338 字，大约阅读时间需要 7 分钟。

讲解

本篇博文其实只是笔者个人的做法复习笔记罢了，

如果是为学习后缀自动机不小心点进来的看官们，

我推荐先看 ，名副其实。

实现

0.Structure

struct SAM{
   	int s[MAXC],fa;	int len;	SAM(){
   memset(s,0,sizeof(s));fa=len=0;}}sam[MAXN<<1];

1.建立：插入点

新点 $c_{(char)}$ 插入末端 → $le{n}_{np=++cnt}$ 赋为 $le{n}_{p=last}+1$

$②$ 找到第一个 $s[c]$ 记为 $q$ →

$Case\#2$ $le{n}_q>le{n}_p+1$，$endpo{s}_{np}$(位置集) 不是 $endpo{s}_q$ 的子集，不能连父亲，于是把 $q$ 拆了：

图示：

模板：

int las = 1,cnt = 1;int f[MAXN<<1]; //extravoid addsam(int c) {
   	int p = las; int np = (las = ++ cnt); 	f[np] = 1; //extra	sam[np].len = sam[p].len + 1;	for(;p && !sam[p].s[c];p = sam[p].fa) sam[p].s[c] = np;	if(!p) sam[np].fa = 1;	else {
   		int q = sam[p].s[c];		if(sam[q].len == sam[p].len + 1) sam[np].fa = q;		else {
   			int nq = ++ cnt;sam[nq] = sam[q];			sam[nq].len = sam[p].len + 1;			sam[np].fa = sam[q].fa = nq;			for(;p && sam[p].s[c] == q;p = sam[p].fa) sam[p].s[c] = nq;		}	}	return ;}

2.处理出现次数

注意到上面注释 //extra 的地方，即是出现次数的初步处理

模板：

vector
   
     g[MAXN<<1];void build_Parent_Tree() {
   	for(int i = 2;i <= cnt;i ++) g[sam[i].fa].push_back(i);}void dfs(int x) {
   	for(int i = 0;i < (int)g[x].size();i ++) {
   		dfs(g[x][i]);		f[x] += f[g[x][i]];	}}
   

3.用法

• SAM 和 Parent Tree 高度统一，SAM 上每个点存的出现次数同时也是 Parent Tree 上每一等价类中所有子串出现次数
• Parent Tree 中的父边在字符串匹配时可以当 AC 自动机中的 fail 边用
• 由于 SAM 是个 DAG ，可以进行 DAG 的各种操作，拓扑、DP、…
• $(Tobecontinued)$

转载地址：https://blog.csdn.net/weixin_43960414/article/details/111990471 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！