SPOJ.com - Problem DISUBSTR

DISUBSTR - Distinct Substrings

#suffix-array-8

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 <= 1000

Output

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

Example

Sample Input: 2 CCCCC ABABA Sample Output: 5 9

Explanation for the testcase with string ABABA:
len=1 : A,B
len=2 : AB,BA
len=3 : ABA,BAB
len=4 : ABAB,BABA
len=5 : ABABA
Thus, total number of distinct substrings is 9.

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 Next >

	Crazyxx: 2015-05-04 08:32:02 Suffix_Automaton XD
	the_imp: 2015-02-14 06:17:04 what should be the answer for "AbABa"..... i'm using suffix array and lcs getting wa Last edit: 2015-02-14 06:50:44
	Rajat (1307086): 2015-01-28 12:19:51 Got a new definition of sub string: "prefix of all suffixes of a string is sub string."
	Kishlay Raj: 2015-01-25 06:35:44 learnt alot
	gamer496: 2014-12-24 21:18:01 finally after 3 days of understanding suffix array and lcp and numerous wrong answers
	surayans tiwari(http://bit.ly/1EPzcpv): 2014-12-22 11:22:16 used set vector and with just 30 lines of code got it accepted
	numerix: 2014-11-15 06:18:04 Another problem that switched from Pyramid to Cube within the last 12 hours. Time limit seems to be adjusted "automatically", but should be less strict for slower languages. The rejudge process is either incomplete or doesn't work correctly as there are still AC Python submissions that use psyco (not supported on Cube), while others (e.g. mine ...) are no longer valid. --ans(Francky)--> I suspect too that rejudge is incomplete... I saw that when PRIME1 switched. Edit : but it seems there's still Py2-psyco submissions for PRIME1 ; can you confirm or not ? There shouldn't be no more such AC one, right ? Reply of numerix: Yes, there are AC psyco submissions left in PRIME1 and also some other problems. According to time limit here: There is an actual AC Python submission with PyPy, so it is possible to get AC with Python if algorithm is well designed. Last edit: 2014-11-16 16:32:47
	Varun Gambhir: 2014-09-04 08:12:10 Suffix Array :)
	KevinMercer: 2014-08-14 07:52:38 He's wrong!There're sth far from 'A'~'Z'!
	Enterprise: 2014-08-14 07:48:59 I think strings have chars besides capital letters, for I kept getting wa until I expand letter array to all chars.

Submit solution!

Added by:	Prasanna
Date:	2006-01-13
Time limit:	0.5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: NODEJS PERL6 VB.NET
Resource:	ByteCode '06