DISUBSTR - Distinct Substrings
Given a string, we need to find the total number of its distinct substrings.
T- number of test cases. T<=20;
Each test case consists of one string, whose length is <= 1000
For each test case output one number saying the number of distinct substrings.
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.
used set vector and with just 30 lines of code got it accepted
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.
Suffix Array :)
He's wrong!There're sth far from 'A'~'Z'!
I think strings have chars besides capital letters, for I kept getting wa until I expand letter array to all chars.
DP (prefix[:i]) + Z-Function => O(n^2) get AC.
My soln got ac in subst1 but getting wa here any trick???
nice 1 ...learnt a new Data Structure..thanx SPOJ
@swati gupta : beautiful indentation, opened the code but couldn't dare to read it.
using suffix array+lcp...using radix sort instead of sort()