【Hihocoder1449】后缀自动机三·重复旋律6


题意

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

分析

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

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

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

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

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

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

 

 

You may also like

【TJOI2015】弦论

【AHOI2013】差异

LEAVE A COMMENT

Statistics

  • 1
  • 16,384

Categories

Archive

Comments