sajalhsn13's blog

By sajalhsn13, history, 5 years ago, In English

Hello everyone,

I am trying to solve this problem. If I can build the LCP array with O(n) complexity I can easily solve it. But building LCP array requires suffix array. I know the O(n*logn*longn) algorithm. But It will give me TLE in this problem. I need the O(n) algorithm to build suffix array. I searched for it and get a paper which is too complex to understand for me. Can anyone give me a simple and well explained tutorial to build suffix array with O(n) time? It will be great help for me.

Thank you.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

You should also try solving with the algorithm. Its constant is very good in comparison with the O(n) one, and it may pass.

»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

No, you don't need suffix array. Try to learn easier techniques

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    actually I have learnt the O(n*long*long) suffix array algorithm 3 or 4 days ago and found some problems in spoj which can be solved with suffix array. Those may be solved with other ways. But I am trying to practice suffix array and thats why I want to solve it with this algorithm.

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

    Which easier techniques can be useful? I need hints.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Spoiler
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I used suffix array with radix sort which time complexity is O(nlogn). If hashing + binary search is used how it will give better complexity?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Not better complexity, better constant factor.