jugal_sahu's blog

new distingct substring (spoj)
By jugal_sahu, 10 years ago, In English

problem link : link

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes i want please give me your java code and explain how u optimized it....thanks

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This was my code for the easy problem

      http://ideone.com/0BbVs3

      The suffix array code is taken from competitive programming 3 and it gave me TLE for the hard version of the problem. So, I searched the internet for another suffix array implementation and actually I used it with the same approach.

      Here is the code

      http://ideone.com/kW5UFT

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply