DISUBSTR  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 <= 1000
Output
For each test case output one number saying the number of distinct substrings.
Example
Sample Input:
2
CCCCC
ABABA
Sample Output:
5
9
Explanation for the testcase with string ABABA:
len=1 : A,B
len=2 : AB,BA
len=3 : ABA,BAB
len=4 : ABAB,BABA
len=5 : ABABA
Thus, total number of distinct substrings is 9.
hide comments
surayans tiwari(http://bit.ly/1EPzcpv):
20141222 11:22:16
used set vector and with just 30 lines of code got it accepted 

numerix:
20141115 06:18:04
Another problem that switched from Pyramid to Cube within the last 12 hours. Time limit seems to be adjusted "automatically", but should be less strict for slower languages.


Varun Gambhir:
20140904 08:12:10
Suffix Array :) 

KevinMercer:
20140814 07:52:38
He's wrong!There're sth far from 'A'~'Z'! 

Enterprise:
20140814 07:48:59
I think strings have chars besides capital letters, for I kept getting wa until I expand letter array to all chars. 

maniAC:
20140514 15:04:50
DP (prefix[:i]) + ZFunction => O(n^2) get AC. 

Pratik kumar:
20140328 17:25:05
My soln got ac in subst1 but getting wa here any trick??? 

innovolt:
20140312 04:18:17
nice 1 ...learnt a new Data Structure..thanx SPOJ 

AvmnuSng:
20140206 20:22:15
@swati gupta : beautiful indentation, opened the code but couldn't dare to read it. 

swati gupta:
20140206 19:16:37
using suffix array+lcp...using radix sort instead of sort()

Added by:  Prasanna 
Date:  20060113 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  ByteCode '06 