2003 Canadian Computing Competition, Stage 1

Problem S4: Substrings

How many distinct substrings does a given string S have?

For example, if S = "abc", S has 7 distinct substrings: "", "a", "b", "c", "ab", "bc", "abc". Note that the empty string and S itself are considered substrings of s.

On the other hand, if S = "aaa". S has only 4 distinct substrings: "", "a", "aa", "aaa".

Input

The first line of the input file contains N, the number of test cases. For each test case, a line follows giving S, a string of from 1 to 5000 alphanumeric characters.

Output

Your output consists of one line per case, giving the number of distinct substrings of S.

Grading

Sample Input

2
abc
aaa

Sample Output

7
4

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 15.00s
Memory Limit: 256M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

watch out for the endl.... 

Ok how do we do this problem (without using tries or suffix arrays or any 1337 thing that only brian, hanson, jacob know and are capable of coding becuase they're experienced)?

It used to be doable using only loops, but I added an extra test case, so now Hanson's loops-only solution gets 180/200.

The suffix array solution is the easiest.

First you should come up with the loops solution - it's completely doable.
(BTW it seems you changed it to 150/200)

There can now be up to 5000 characters.
(Now sets/maps will not work - no matter what.)
Again the points will revert to 20, so no one loses (in fact most of you win, since partial marks are now on)

it worked on my computer.

can someone help :P? 

Notice your memory use: it's getting close to 256MB!
Uncaught exception can mean a lot of things, and one of those things is running out of memory.

damn these uncaught exceptions