首页 > 题解 > spoj 8222 NSUBSTR – Substrings

spoj 8222 NSUBSTR – Substrings


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|.

Input

String S consists of at most 250000 lowercase latin letters.

Output

Output |S| lines. On the i-th line output F(i).

Example

Input:

ababa

Output:

3
2
2
1
1

题解

肯定先建个SAM

对于每个串维护一个siz,表示这个串出现的次数,然后统计一下就好啦


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×