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
prince_batra:
20180209 12:43:04
Can string also contain lowercase char. ? 

seyedssz:
20170824 14:04:32
0.02 s with O(n*log^2) 

tnorris:
20170701 02:49:24
Naive Solution is O(n^2 * logn)  hits time limit


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