【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】差异

一条评论

  • Dau tu coin
    十月 25, 2019 at 11:02 下午

    Great post. I was checking continuously this blog and I am impressed!
    Very useful info specially the last part 🙂 I care for such info much.
    I was seeking this particular information for a very long time.
    Thank you and best of luck.

LEAVE A COMMENT

Statistics

  • 0
  • 2,011

Categories

Archive