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 ith line output F(i).
Example
Input:
ababa
Output:
3
2
2
1
1
hide comments
treenipples:
20210626 20:09:27
can be solved with Suffix array + Largest rectangular area in histogram concept Last edit: 20210626 20:09:53 

likhon5:
20200609 13:34:29
can anyone provide some more tricky test case? Last edit: 20200609 13:42:16 

iloly:
20200131 02:56:13
O(nlogn) is ok 

dxymaster2002:
20180307 14:38:01
I am an archaeologist. 

cjsoft:
20160718 09:49:37
Suffix AutoMaton is needed 

humeay:
20151123 12:13:56
my topsort+dp passed 

lu:
20150528 09:12:01
I got AC only if my program is O(n) 

Siarhei Kulik:
20110822 15:06:20
O(N) was expected. 

蓝细菌:
20110822 15:06:20
too strict time limit,my nlogn algorithm can't pass. 

[retired]grayluck:
20110822 15:06:20
the time limit is too strict....My O(nlogn) got TLE.. 
Added by:  Sergey Kulik 
Date:  20110127 
Time limit:  0.100s1s 
Source limit:  44444B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Immagination 