CCC '03 S4 - Substrings

View as PDF

Submit solution

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

Problem type
2003 Canadian Computing Competition, 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
    ScriptKitty  commented on July 17, 2018, 4:12 p.m. edit 2


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

    What are the constraints are N?

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

      1 <= N <= 5

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

      N is a real number.

  • -6
    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.

  • 2
    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.

    • 9
      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).