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

new distingct substring (spoj)
Автор jugal_sahu, 10 лет назад, По-английски

problem link : link

I have already solved distinct substring (spoj : link) but new distinct substring have strict timelimit.Please give me hint.....thanks

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

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

Suffix automaton solves this(maybe that is overkill, not sure).

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

You can solve it in O(NlogN) with Suffix Array + Longest Common Prefix Array. Since same substrings will be in adcajent indexes in suffix array, you can easily eliminate them. I mean first calculate the number of same substrings then substract it from (N*(N+1))/2

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

    Actually there is a problem distinct substring (easy one link:distinct substring). I have solved it using suffix array but new substring has strict timelimit.....please suggest

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

      O(NlogN) will work with N <= 50,000. But if you want more optimal you can get suffix array and LCP array in O(N).

      → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I have solved both actually using java 2 years ago using suffix array and LCP. I used a faster Suffix Array construction to pass the hard one. Do you want it?

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

Also counting the paths of a suffix automaton will solve it in linear time.

→ Ответить