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".
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.
Your output consists of one line per case, giving the number of distinct substrings of S.
Grading50% of test cases will have l (the length of the string) ≤ 1,000.
For all cases, l ≤ 5000.
2 abc aaa
Point Value: 20 (partial)
Time Limit: 15.00s
Memory Limit: 256M
Added: Sep 30, 2008
- Data Structures
- String Manipulation
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
The suffix array solution is the easiest.
(BTW it seems you changed it to 150/200)
(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)
can someone help :P?
Uncaught exception can mean a lot of things, and one of those things is running out of memory.