-1

Suppose I have string str = "aabaa"

Its non repetitive substrings are

  1. a
  2. b
  3. aa
  4. ab
  5. ba
  6. aab
  7. aba
  8. baa
  9. aaba
  10. abaa
  11. aabaa
sunkuet02
  • 2,376
  • 1
  • 26
  • 33
Mohammad Chand Alam
  • 17
  • 8
  • This seems like a homework question. Have you tried to do it yourself? Are you stuck on a particular part? Otherwise, I've done my fair share of coding exercises. – kbunarjo Dec 29 '16 at 03:17
  • Actually this question was asked in a contest on hackerrank .. First and formost i am not able to write code for printing sub strings.. So please tell me how i will print substrings – Mohammad Chand Alam Dec 29 '16 at 03:23
  • 1
    You can't take any substring? Use this http://www.cplusplus.com/reference/string/string/substr/ – Pavel Dec 29 '16 at 03:31
  • Thanks @Pavel , But how will you compare these sub stings with all others to print no repetitive string with minimum time complexity? – Mohammad Chand Alam Dec 29 '16 at 03:39
  • @MohammadChandAlam, if you doesn't have long strings, you can simply add each substring you found to array. To don't add duplicates just check every time if new string already exist in array. It will take O(N^3) memory and O(N^4) time. If you want to do it more effective, use Z-function (http://codeforces.com/blog/entry/3107) – Pavel Dec 29 '16 at 03:50
  • @Pavel Basically this problem was related to minimize time complexity .. String was upto length 100 character.. – Mohammad Chand Alam Dec 29 '16 at 03:57
  • @MohammadChandAlam, 100 chars isn't very much, but if you want an optimal solution, try using Z-function. – Pavel Dec 29 '16 at 03:59
  • Thank you @Pavel I will try to use Z-function. – Mohammad Chand Alam Dec 29 '16 at 04:01
  • @MohammadChandAlam You could use a `std::set` or `std::unordered_set` instead of an array. Then you don't need to check for duplicates. – PaulMcKenzie Dec 29 '16 at 04:46

1 Answers1

3

  1. Compute the suffix array and the longest common prefix array thereof.

    a
 1
aa
 2
aabaa
 1
abaa
 0
baa

  2. Return (n+1)n/2, the number of substring bounds, minus the sum of the longest common prefix array.

    (5+1)5/2 - (1+2+1+0) = 15 - 4 = 11.
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120