题意

字符串 \(S\) 中,求出长度为 \(k(1\le k\le |S|)\) 的子串出现次数最多的出现了几次。

分析

每个状态\(x\)所表示的所有子串的出现次数都相同。

我们把原始点(没有被拆分,或者拆分前的点)标记为\(1\),其余为\(0\)。

如果一个状态\(x\)出现了,显然它的所有\(link\)前缀都出现了。

利用拓扑序,做一个前缀和,显然就是每个状态的出现次数。

每个状态\(x\),所代表的子串的长度范围为\([len[link[x]]],len[x]\)。

又显然,不同长度的最大出现次数递减,所以我们只需要在\(len[x]\)处打标记,再倒着更新一遍就好了。

 

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注