SUBST1  New Distinct Substrings
Given a string, we need to find the total number of its distinct substrings.
Input
T number of test cases. T<=20; Each test case consists of one string, whose length is <= 50000
Output
For each test case output one number saying the number of distinct substrings.
Example
Input: 2 CCCCC ABABA Output: 5 9
hide comments
deerishi:
20160716 00:24:06
Why does O(nlogn) (suffix array using radix sort) time out ? Last edit: 20160716 00:24:19 

ravi:
20160322 16:36:41
nlognlogn =tle nlogn=ac better to learn nlogn found this useful


Dhawal Harkawat:
20160120 17:07:32
Optimized nlog^2n gets passed in 0.12s, while nlogn passes in 0.14s. I dont know why?? 

humanity:
20151230 22:43:11
nlogn(used radix sort everytime) with pointer optimisation got accepted though 0.27 seconds :( ,any ideas for better implementation Last edit: 20151230 22:43:54 

Divyansh Shukla:
20151223 10:47:00
For java, use the O(n) version. It got AC in 0.15s 

stormblessed91:
20150826 21:13:54
Takes 0.5s in java! anybody managed in java? 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150821 19:33:59
Seems that Rodrigo Horruitiner was right and my previous summary comment on this problem is wrong, O(n) is slower than O(n*log(n)) because of radix constant :p 

poojan :
20150818 19:17:58
O(n*log n*log n) giving tle: 

Obliterator:
20150801 20:56:08
Yup. had to use suffix array with counting sort to get AC. Still wondering how did Manoj Kumar get AC with brute force.


eightnoteight:
20150611 19:29:20
O(n*log^2(n)) with out using IO optimization got AC.. 
Added by:  Hoang Hong Quan 
Date:  20060118 
Time limit:  0.280s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL 6 VB.net 
Resource:  Base on a problem in ByteCode06 