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
Daniel:
20120821 09:51:36
Suffix Array can do it!It's the same as the problem 694.Suffix Array can solve it within only 0.4s. 

bean:
20120615 04:02:04
Why can I get AC in this problem but not in problem 694? Last edit: 20120615 04:02:54 

Gaurav Menghani:
20110803 13:41:26
I had to replace strlen by pointer arithmetic, and sort by qsort to get AC. Sigh :( 

Jitendra:
20110728 08:19:53
qsort is faster than stl sort. stl sort gives tle while qsort soln accepted :) 

Thomas Dybdahl Ahle:
20110709 22:55:14
I would say "" is a substring of any string, but I notice it isn't counted in the examples. Or maybe its the string itself that isn't counted as a substring? 

Leopoldo Taravilse:
20100602 12:51:09
Do the strings contain the ' ' char? 

lccycc:
20100225 15:45:52
length is <= 50000


[Rampage] Blue.Mary:
20100225 15:40:53
Read the problem statement (especially the input section) CAREFULLY 

lccycc:
20100225 15:25:32
What's the difference between this problem and 694? 

Ray:
20091130 13:05:48
The time limit should be loosen. For Python(Psyco), it is nearly impossible to AC by Suffix Array. 
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 