后缀自动机

# 构建 通过$SAM$的性质来构建 根据$parent$树确定的等价类及之间的父子关系 儿子是根据父亲代表的最长串前面加字符得到的 后缀自动机的节点和$parent$树共用节点 后缀自动机上的边表示这个字符串向后加一个字符的得到的新串 且**从根节点到达某个节点的全部路径为它的等价类所代表的所有字符串** 构建时一个个插入字符 对于一个新的字符$c$ 多了一个位置为$\{n\}$的等价类 要得到所有到达这个节点的字符串 就要先将$p$（上一个字母的节点）连上边 再跳它的父亲 （遍历所有后缀）看有没有$c$这个节点 如果没有就直接连上 相当于加到了新节点的$endpos$集合中 如果有 得到的第一个$q$就可能是$np$的父亲 因为这个点是最深的、后缀和$np$一样的点 如果$len(q)==len(p)+1$就直接是父亲了 如果比他大 说明所有比$len(p)+1$大的字符串不是$np$的后缀 因为如果是 则它$-1$一定是 且比$p$长 应该比$p$先跳到 所以这时候就把$q$拆一下点 把含等价类$\{n\}$的、长度为$p+1$的$nq$作为父亲 并向上调整连向$q$的边就行了 **构建过程** **看图**       #### 上代码 #### 插入（广义$SAM$） 普通的把$if$去掉 插入时 这个点的$id$永远插在$last$上 广义SAM多加一个特判 注意特判新建$nq$时和原来不同 $last$要等于$nq$ ```cpp void extend(int c,int id){ int p=last; if(dian[p].ch[c]){ int q=dian[p].ch[c]; if(dian[q].len==dian[p].len+1){last=q;s[last].insert(id);return;} else{ int nq=++tot;last=tot; dian[nq]=dian[q];dian[nq].len=dian[p].len+1; dian[q].fa=nq; for(;p&&dian[p].ch[c]==q;p=dian[p].fa)dian[p].ch[c]=nq; s[last].insert(id); } return; } int np=++tot;last=np; dian[np].len=dian[p].len+1;s[last].insert(id); for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np; if(!p)dian[np].fa=1; else{ int q=dian[p].ch[c]; if(dian[q].len==dian[p].len+1)dian[np].fa=q; else{ int nq=++tot; dian[nq]=dian[q];dian[nq].len=dian[p].len+1; dian[q].fa=dian[np].fa=nq; for(;p&&dian[p].ch[c]==q;p=dian[p].fa)dian[p].ch[c]=nq; } } } ``` # 题 ## [[HEOI2015]最短不公共子串](https://www.luogu.com.cn/problem/P4112) 构建出序列自动机和$SAM$ $BFS$求出第一个符合要求的长度即可 ## [[十二省联考2019]字符串问题](https://www.luogu.com.cn/problem/P5284) 建立反串的$SAM$ 定位出$A,B$串的节点位置，直接利用$Parent$树边加上支配关系构建$DAG$ $DP$即可 对于后$20\%$对于一个点要按照$len$为第一关键字 $len$相同时$A$在下$B$在上拆点 边权存到支配边上 最后一个点的贡献求一下每个$B$对应的子树最大值即可 ## [[NOI2018]你的名字](https://www.luogu.com.cn/problem/P4770) 每一个询问 建立两个$SAM$ 先把小串放到大串的$SAM$上跑一边 利用线段树合并求出$endpos$集合 得出小串每个点开始的最长限制长度（即当前位置$i$在大串上匹配的长度就是这个串第$i$位往前与大串匹配的最长长度 向上跳$fail$即在前面删除字符 得到和下一位匹配的状态**注意这里和AC自动机上匹配比较像 都是儿子从父亲继承信息 查询父亲而不是儿子们 其实本质SAM的Parent树就相当于SAM所有子串的AC自动机的Fail树**） 把这个限制长度传到小$SAM$的$np$节点上 在每个节点上通过$len$计算一下非限制的本质不同的子串个数加起来即可 注意小串在大串上跳的过程 可以直接从跳到的完全限制节点开始匹配 ## [LOJ#6041. 「雅礼集训 2017 Day7」事情的相似度](https://loj.ac/problem/6041) $LCP$即树上点的$LCA$ 对于整体考虑 最后产生贡献的后缀出现位置为相邻的两个显然不会更劣 先用$set$启发式合并求出$endpos$集合 把相邻的作为点记录 最后就是一个二维数点求矩形内最大值的过程 用离线的树状数组即可实现 ## [[BZOJ3413]匹配]( https://lydsy.com/JudgeOnline/problem.php?id=3413 ) 转化一下 答案就是可匹配区间内每个前缀出现的次数之和 先用线段树合并求出$endpos$ 再用小串在$SAM$上跑 跑到一个点此时匹配的为小串的一个前缀（注意 不跳$fa$ 否则不是前缀）通过$endpos$集合算出在可行区域内出现了几次 加上去就行了 ## [[BZOJ3879]SvT]( https://lydsy.com/JudgeOnline/problem.php?id=3879 ) 询问若干个前缀两两之间的$LCP$ 反过来变成后缀 求一堆点的$LCA$ 用个虚树就行了 ## [CF700E Cool Slogans]( https://www.luogu.com.cn/problem/CF700E ) $DP$设$f[i]$表示从上而下到达当前点能够满足条件的最优值 只需要检查父亲节点是否在当前串中出现过两次就行了用$endpos$加上线段树合并来判断 ## [[USACO17DEC]Standing Out from the Herd]( https://www.luogu.com.cn/problem/P4081 ) 建出广义$SAM$ 用$set$处理下$endpos$ 看出现是否唯一就行了 ## [CF666E Forensic Examination]( https://www.luogu.com.cn/problem/CF666E ) 询问离线 广义$SAM$加上线段树合并就行了 ## [[BZOJ1396]识别子串]( https://www.lydsy.com/JudgeOnline/problem.php?id=1396 ) 找所有叶子节点 用它们的长度更新序列上的答案 要一个区间加 一个类似于区间加等差数列 开两个线段树维护 具体没有实现(upd:貌似直接扫一遍就行了 不用两棵树？) ## [[SDOI2016]生成魔咒]( https://www.luogu.com.cn/problem/P4070 ) 动态维护一下``dian[i].len-dian[dian[i].fa].len``的大小即可 ## [[CTSC2012]熟悉的文章]( https://www.luogu.com.cn/problem/P4022 ) 在广义$SAM$上求出当前位置向前最大匹配长度 然后二分答案加上单调队列优化就行了 注意单调队列到一个点加入的决策为$i-lim$ 所以先加入决策再求$f$ ## [CF235C Cyclical Quest]( https://www.luogu.com.cn/problem/CF235C ) 先倍长 在匹配时向上跳到$len\le n$ 把答案累加即可 ## [[ZJOI2015]诸神眷顾的幻想乡]( https://www.luogu.com.cn/problem/P3346 ) 一棵树 但叶子$\le20$ 分别作为根$dfs$出一些字符串 建立广义$SAM$直接算答案 ## [BZOJ3277串]( https://www.lydsy.com/JudgeOnline/problem.php?id=3277 ) 建立广义$SAM$ 利用$set$可以去重的性质合并$endpos$集合（集合内存为哪个串的子串）记录出现次数$\ge k$的 计算一下贡献就行了 ## [BZOJ2555SubString]( https://www.lydsy.com/JudgeOnline/problem.php?id=2555 ) $LCT$维护$parent$树 动态维护子树大小就行了 ## [[AHOI2013]差异]( https://www.luogu.com.cn/problem/P4248 ) 化一下式子 发现与任意两个串的后缀长度有关 直接在$LCA$处计算贡献就行了 ## [[TJOI2015]弦论]( https://www.luogu.com.cn/problem/P3975 ) 两种情况分开讨论 分别为算不算$endpos$集合大小 $DP$出从每个点开始的字符串个数 凑出第$k$个 ## 一些技巧 1.$np$节点在传入时可以传进去很多信息 2.向上跳$fa$的过程可以倍增实现 3.定位$L-R$的位置 记录$R$插入时的节点编号 再向上倍增地找