题意翻译
你得到一个字符串,最多由25万个小写拉丁字母组成。我们将 F(x)定义为某些长度X的字符串在s中出现的最大次数,例如字符串’ababaf’- F(x),因为有一个字符串’ABA’出现两次。你的任务是输出 F(x)每一个I,以使1<=i<=|S|.
题目描述
You are given a string S which consists of 250000 lowercase latin letters at most. We define F(x) as the maximal number of times that some string with length x appears in S. For example for string ‘ababa’ F(3) will be 2 because there is a string ‘aba’ that occurs twice. Your task is to output F(i) for every i so that 1<=i<=|S|.
输入输出格式
输入格式:
String S consists of at most 250000 lowercase latin letters.
输出格式:
Output |S| lines. On the i-th line output F(i).
输入输出样例
输入样例#1: 复制
ababa
输出样例#1: 复制
3 2 2 1 1
我的做法仍然是首先拓扑排序 然后直接倒推一下dp 注意可能最后dp数组需要倒推一遍 因为我拓扑排序的时候处理出的dp数组应该都只是针对那个节点对应的right集合的最长的那个值
update 重新思考一下觉得dp数组并不需要倒着推 因为仔细观察拓扑排序的时候即可知道我一定是大的更新小的 那么只有在par树上才会存在这样的对答案有贡献的结果 那么即使一个节点在par树上可能和上一个节点的长度差距很大 但是因为right集合是有包含关系的所以转移到我的情况上的那些节点
如果有错qwq请联系本蒟蒻 联系方式在(elijahqi.win)的个人资料页

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论