CF竞赛题目讲解_CF873F(后缀自动机+子串出现次数)
2022-10-03 16:04 作者:Clayton_Zhou | 我要投稿
https://codeforces.com/contest/873/problem/F
题意:
给定一个串s,其中一些位置被禁止。定义一个子串的出现次数为,其结束位置不被禁止。
求s的所有子串中,长度*出现次数的最大值。
题解:
后缀自动机
计算每个子串的出现次数,去除那些子串,其结束位置是 被禁止。
关键点是,找到那些子串,其结束位置被禁止。