SUBST1 - New Distinct Substrings

no tags 

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
ravi: 2016-03-22 16:36:41

nlognlogn =tle nlogn=ac better to learn nlogn found this useful
http://stackoverflow.com/questions/34402080/suffix-array-construction-on-logn-competitive-programming-3-steven-halim
take care case CCCCC with sentinel character

Last edit: 2016-03-22 16:37:50
Dhawal Harkawat: 2016-01-20 17:07:32

Optimized nlog^2n gets passed in 0.12s, while nlogn passes in 0.14s. I dont know why??

humanity: 2015-12-30 22:43:11

nlogn(used radix sort everytime) with pointer optimisation got accepted though 0.27 seconds :( ,any ideas for better implementation

Last edit: 2015-12-30 22:43:54
Divyansh Shukla: 2015-12-23 10:47:00

For java, use the O(n) version. It got AC in 0.15s

rini22: 2015-08-29 08:45:08

remove strlen

stormblessed91: 2015-08-26 21:13:54

Takes 0.5s in java! anybody managed in java?

(Tjandra Satria Gunawan)(曾毅昆): 2015-08-21 19:33:59

Seems that Rodrigo Horruitiner was right and my previous summary comment on this problem is wrong, O(n) is slower than O(n*log(n)) because of radix constant :p

poojan : 2015-08-18 19:17:58

O(n*log n*log n) giving tle:

Obliterator: 2015-08-01 20:56:08

Yup. had to use suffix array with counting sort to get AC. Still wondering how did Manoj Kumar get AC with brute force.
EDIT: Apparently we have to use Kasai's algorithm in LCP array construction to get AC in O(nlog^2n)

Last edit: 2015-08-02 14:55:13
abhijeet: 2015-07-29 19:43:21

If you get tle for nlogn*logn
1. remove std::sort to qsort
2. remove strlen(use ur own length method)


Added by:Hoang Hong Quan
Date:2006-01-18
Time limit:0.280s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL 6 VB.net
Resource:Base on a problem in ByteCode06