洛谷 P3804 模板(SAM)
发布时间
阅读量：
阅读量
【模板】后缀自动机 (SAM)
题目描述
对于一个仅由小写字母构成的字符串 S，请计算所有出现次数大于 1 的子串，将其出现次数与子串长度相乘后的结果求出最大值。
输入格式
给定一个字符串 S，其仅由小写字母组成，且每行仅包含一个此类字符串。
输出格式
一个数值，即为目标解。
样例分析与呈现
样例输入 #1
abab
样例输出结构解析
4
提示
当数据量占比为 10 \% 时，集合 S 的元素个数不超过 1000。
若数据量占比达到 100 \%，则集合 S 的元素个数范围为 1 到 {10}^6。
后缀自动机， 需要维护3个数组
ch[x][c] 存节点x转移边终点
fa[x] 存节点x的链接边终点
len[x] 存节点x的最长串的长度
后缀链接树, 抽离图中的链接边
合法性： 子节点的最短串的最长后缀 = 父节点的最长串
1、 节点x的子串长度： 最长 len[x], 最短 len[y] + 1 全部评论 (0)
还没有任何评论哟~