SUBST1 - New 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 <= 50000


For each test case output one number saying the number of distinct substrings.




hide comments
yuhta: 2018-10-31 17:09:12

Test is weak. Got 0.05 using naive sort (n^2*log(n)).

karan_yadav: 2018-07-20 06:30:06

Suffix array using Radix sort will get you through 0.01s

prince_batra: 2018-02-09 12:43:04

Can string also contain lowercase char. ?

seyedssz: 2017-08-24 14:04:32

0.02 s with O(n*log^2)

tnorris: 2017-07-01 02:49:24

Naive Solution is O(n^2 * logn) - hits time limit
Doubling Solution is O(n * log^2 n) - hits time limit (might not in a faster language)
There are faster solutions in O(n * logn) and O(n). According to comments here, thats the time threshold for this problem.

Last edit: 2017-07-04 00:57:03
jaijoshi: 2017-04-29 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.
Taking help from :

sultania23: 2017-03-26 12:05:39

n*logn*logn AC

sultania23: 2017-03-26 12:04:59

2 days to figure out by taking little help..nice problem

deerishi: 2016-07-16 00:24:06

Why does O(nlogn) (suffix array using radix sort) time out ?

Last edit: 2016-07-16 00:24:19
ravi: 2016-03-22 16:36:41

nlognlogn =tle nlogn=ac better to learn nlogn found this useful
take care case CCCCC with sentinel character

Last edit: 2016-03-22 16:37:50

Added by:Hoang Hong Quan
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