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 >

	jahid_hasan17: 2020-10-12 18:34:34 it can be done using suffix array(nlogn),suffix automaton(n)
	avsd_47: 2020-08-10 09:34:16 use fast i/o if u r facing issue in cpp
	anish1712: 2020-06-21 16:59:27 Can someone let me know when I use total number of substrings as (n+1)*n/2 it fails but when I use summation of n-suffArray[i] it passes
	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 nlognlogn 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 : https://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arrays
	sultania23: 2017-03-26 12:05:39 nlognlogn AC