后缀自动机模板

yaolong88163 14 0 PDF 2021-01-15 16:01:02

入门推荐博客:https://www.luogu.com.cn/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie 简单介绍一下各个参数:构造SAM时强制在线,一个一个字母按照顺序依次插入 tot:节点数 last:最长前缀所属编号 ch数组:类似于字典树存边,存的是在当前节点末尾添加一个字符后所能到达的状态 fa:后缀链接,简单来说就是与当前节点有相同的后缀,但是最大长度比当前节点小的结点 len:每个节点所储存的字串的最大长度 fa(i)结点与 i 结点的关系: 到达点 i 的所有字符串的长度都必然大于到达 fa(i) 的所有字符串的长度,且到

用户评论
请输入评论内容
评分:
暂无评论