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 >

	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2015-01-02 22:42:54 Here is my summary: O(nlog^2(n)) --> definitely TLE even pointer opti used. O(nlog(n)) --> longer code, AC O(n) --> there're exist algorithm with this amortized complexity but very painful to code. I'm sure I this O(n) can get AC in 0.00s
	Gaurav Babbar: 2014-10-23 21:11:03 SAM is givig TLE! what is the size of the input alphabet set?? ---- AC after optimisatons :) Last edit: 2014-10-24 21:15:36
	Varun Gambhir: 2014-10-23 18:59:07 nlognlogn algorithm for building suffix array gives tle :(
	Ashish Kumar: 2014-05-13 14:48:00 Used suffix array with qsort function but it is giving tle?? Last edit: 2014-05-13 14:48:16
	yhylord: 2014-04-26 06:07:37 Can SAM solve this problem? If S contains all characters in ASCII,then SAM will get MLE(TLE)... -------- Now I've got TLE. How many cases does it has? Last edit: 2014-04-29 14:35:19
	innovolt: 2014-03-12 04:21:36 simple 1 .........sufffixxxxx array
	aar: 2013-08-28 12:53:17 Suffix Array with O(n * logn *logn) is accepted...
	jimmy: 2013-07-17 07:26:55 O(N*Log(N)^2) gets TLE.. @Jitendra i tried using qsort too. it gives TLE
	aqfaridi: 2014-03-07 11:01:43 pointer arithmetic to speed up..
	Abdullah Enes ÖNCÜ: 2013-04-18 04:35:07 why I get a RTE?