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
jaijoshi:
20170429 21:39:52
I am using n*logn*logn solution with array of structure for buiding suffix array and still getting TLE. and for lcp i am using kasai's algo. Please help me.


sultania23:
20170326 12:05:39
n*logn*logn AC 

sultania23:
20170326 12:04:59
2 days to figure out by taking little help..nice problem 

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 
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 PERL6 VB.NET 
Resource:  Base on a problem in ByteCode06 