DISUBSTR - Distinct Substrings


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.


hide comments
Jarily: 2013-03-23 08:27:04

newbie go past

shen: 2013-03-03 10:58:04

orz CaiG

fjh: 2013-02-03 14:16:46

When I add 'memset',my programme accepted.And when I don't add it,my programme wrong answer.Why?

Owen: 2013-01-16 06:41:56

Độc cô cầu bại :How you dynamic programming?

Sanjary Rahman: 2012-11-23 18:20:06

Doubly Algo of suffix array took 0.01s for me :)

Raghavendran Ramachandran: 2012-10-03 09:40:32

Can the string contain characters other than A-Za-z ?

Arun Lakshman: 2012-08-30 13:59:09

http://www.spoj.pl/problems/SUBST1/

Dunno: 2012-08-15 21:57:46

welll, O(N^2) works since constraint is pretty small.

陈迪: 2012-05-26 09:42:39

suffix arr && height arr

fox_pro: 2012-05-04 06:51:40

can hash work?


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