SPOJ.com - Problem SUBST1

SUBST1 - New Distinct Substrings

#suffix-array-8

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.

Input:
2
CCCCC
ABABA

Output:
5
9

< Previous 1 2 3 4 5 6 Next >

	eightnoteight: 2015-06-11 19:29:20 O(n*log^2(n)) with out using IO optimization got AC..
	Martin Radev: 2015-06-10 10:07:03 Note that the symbols in the input are not only in A...Z. Suffix tree is fast enough using McCreight's construction algorithm.
	Manoj Kumar Regar: 2015-05-25 16:02:44 oh gosh! n^2 logn ... naive solution got accepted in 0.06.....
	superfloyd: 2015-05-18 10:04:04 for this problem could you use tries?
	Crazyxx: 2015-05-04 08:37:35 SAM 0.08s & 42M XD
	Sourabh Bansal: 2015-04-20 08:09:17 Suffix Array O(n lg^2(n)) AC .... 0.07 s :)
	mkrjn99: 2015-02-03 06:54:35 nlog^2(n): TLE nlogn: AC
	Rishit Sanmukhani: 2015-02-01 12:30:10 Got AC :) Nice question. n(logn)^2 doesn't pass. We have to make it nlogn. Used counting sort.
	Anmol Pandey: 2015-01-17 17:51:46 O(n*log(n)^2) is AC.
	Rodrigo Horruitiner: 2015-01-06 00:13:36 Actually, the O(n) construction isn't much faster than the O(nlognlogn) one, if at all. The skew algorithm has big constants because of the recursion and the radix sort. Just optimize your code.