Блог пользователя shinghalrishabh

Автор shinghalrishabh, история, 9 лет назад, По-английски

How to find all occurences of each substring in the given string.Please give me some suggestions

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

you can easily make that in O(N*N*N) time using Brute force. Then using hashes it can be reduced to O(N*N). You cAn make that in O(N*N) using KMP.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Z-Function.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If I understood the problem correctly, then using suffix array + lcp should give performance between O(N) and depending on chosen algorithm for searching suffix array.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    actually i asked to have the count for every substring in the string

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Yes, there is no way of doing that in O(N) as there can be ~ N2 different substrings. I was thinking of problem where I had to count number of different substrings.