CCC '03 S4 - Substrings - DMOJ: Modern Online Judge

CCC '03 S4 - Substrings

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2003 Stage 1, Senior #4

How many distinct substrings does a given string $S$ $S$ have?

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

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

Input Specification

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

Output Specification

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

Grading

50% of test cases will have $l$ $l$ (the length of the string) where $l \le 1000$ $l \leq 1000$ . For all cases, $l \le 5000$ $l \leq 5000$ .

Sample Input

Copy

2
abc
aaa

Output for Sample Input

Copy

7
4

Comments

0

jerrycui07 commented on Aug. 2, 2024, 10:01 p.m. ← edited →

Last test case is actually the same string repeated multiple times, so a sub-optimal solution can pass by using a cache. I discovered this by looking at the output, not by finding the actual test case

1

Kirito commented on Jan. 13, 2022, 1:04 p.m.

A new test case has been added and all submissions have been rejudged.

0

myl commented on March 6, 2021, 6:51 p.m.

Are the test strings only alphabetical or do they contain other characters? Is it safe to assume only ASCII characters are used?

5

Tommy_Shan commented on Aug. 3, 2021, 12:27 a.m. ← edit 2 →

A string of from $1$ $1$ to $5000$ $5000$ alphanumeric characters.

1

Kirito commented on March 7, 2021, 1:15 a.m.

Reread the input specification.

-1

daviecar commented on Oct. 27, 2019, 9:42 p.m. ← edited →

I don't think it was supposed to happen, but I just completely brute forced it... (https://dmoj.ca/submission/1661542) Now may I have some tips on how to not be stupid and do it properly?

7

kingW3 commented on Oct. 27, 2019, 10:25 p.m.

Since you solved the problem you can view all the solutions to this problem, you could go to "Best submissions" and find the most readable code and try to understand it, or like someone in the comments mentioned google Suffix Tree.

13

Beautiful_Times commented on Nov. 30, 2017, 3:04 a.m. ← edited →

What are the constraints on $N$ $N$ ?

14

Arman_Lamei commented on July 16, 2019, 2:36 p.m. ← edited →

$1 \le N \le 5$ $1 \leq N \leq 5$

46

InfernoApeZ commented on Nov. 30, 2017, 4:30 a.m. ← edited →

$N$ $N$ is a real number.

54

ArtyKing12 commented on March 29, 2020, 3:24 p.m. ← edit 2 →

When you get WA on a case and notice that n is -5i+0.85

2

raggarwal commented on Nov. 23, 2014, 5:00 a.m. ← edited →

Any tips to optimize the code? test case 3/6/7 are >1 second for me.

18

FatalEagle commented on Nov. 23, 2014, 2:49 p.m. ← edited →

Your algorithm is brute force with a worst-case complexity of $\mathcal{O}(N^4)$ $O (N^{4})$ . There are faster algorithms to solve this (like Suffix Tree).