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
superfloyd:
20150518 10:04:04
for this problem could you use tries? 

Crazyxx:
20150504 08:37:35
SAM 0.08s & 42M XD 

Sourabh Bansal:
20150420 08:09:17
Suffix Array O(n lg^2(n)) AC .... 0.07 s :) 

mkrjn99:
20150203 06:54:35
nlog^2(n): TLE


Rishit Sanmukhani:
20150201 12:30:10
Got AC :) Nice question.


Anmol Pandey:
20150117 17:51:46
O(n*log(n)^2) is AC. 

Rodrigo Horruitiner:
20150106 00:13:36
Actually, the O(n) construction isn't much faster than the O(n*logn*logn) one, if at all. The skew algorithm has big constants because of the recursion and the radix sort. Just optimize your code. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150102 22:42:54
Here is my summary:


Gaurav Babbar:
20141023 21:11:03
SAM is givig TLE! what is the size of the input alphabet set??


Varun Gambhir:
20141023 18:59:07
n*logn*logn algorithm for building suffix array gives tle :( 
Added by:  Hoang Hong Quan 
Date:  20060118 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  Base on a problem in ByteCode06 