CCC '03 S4 - Substrings

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2003 Stage 1, Senior #4

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 Specification

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 Specification

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


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

Sample Input


Output for Sample Input



  • -2
    the_creeper2007  commented on March 25, 2020, 8:12 p.m.

    sad :(

  • -5
    daviecar  commented on Oct. 27, 2019, 5:42 p.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.

    • 4
      kingW3  commented on Oct. 27, 2019, 6: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.

  • 4
    ScriptKitty  commented on July 17, 2018, 4:12 p.m. edit 2


  • 10
    Beautiful_Times  commented on Nov. 29, 2017, 10:04 p.m.

    What are the constraints are N?

    • 9
      Arman_Lamei  commented on July 16, 2019, 10:36 a.m.

      1 <= N <= 5

    • 30
      InfernoApeZ  commented on Nov. 29, 2017, 11:30 p.m.

      N is a real number.

      • 13
        ArtyKing12  commented on March 29, 2020, 11:24 a.m. edit 2

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

  • -8
    anishmahto  commented on Oct. 23, 2016, 8:12 a.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.

  • 1
    raggarwal  commented on Nov. 23, 2014, 12:00 a.m.

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

    • 15
      FatalEagle  commented on Nov. 23, 2014, 9:49 a.m.

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