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

hide comments
treenipples: 2021-06-26 20:09:27

can be solved with Suffix array + Largest rectangular area in histogram concept

Last edit: 2021-06-26 20:09:53
likhon5: 2020-06-09 13:34:29

can anyone provide some more tricky test case?

Last edit: 2020-06-09 13:42:16
iloly: 2020-01-31 02:56:13

O(nlogn) is ok

dxymaster2002: 2018-03-07 14:38:01

I am an archaeologist.

cjsoft: 2016-07-18 09:49:37

Suffix AutoMaton is needed

humeay: 2015-11-23 12:13:56

my topsort+dp passed

lu: 2015-05-28 09:12:01

I got AC only if my program is O(n)

Siarhei Kulik: 2011-08-22 15:06:20

O(N) was expected.

蓝细菌: 2011-08-22 15:06:20

too strict time limit,my nlogn algorithm can't pass.

[retired]grayluck: 2011-08-22 15:06:20

the time limit is too strict....My O(nlogn) got TLE..


Added by:Sergey Kulik
Date:2011-01-27
Time limit:0.100s-1s
Source limit:44444B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Immagination