ayushrocker92's blog

Suffix array
By ayushrocker92, 10 years ago, In English

Hello,am trying to solve this problem on spoj. I am getting wrong answer. Am telling my approach.

It asks for the number of distinct substrings of a string. I have read suffix array and lcp from here. I count number of distinct substring as follows.

1) make suffix array and lcp array

2)count the length of suffix and subtract the lcp from this length of next lexographically sorted suffix

3)summation of all the answers obtained in step 2

More formally ans=0;

    //pos[i]=rank of a number starting at ith position
    //sa[i]=i'th rank string starting at sa[i]
    //n=length of string
    for(i=0;i<n;i++)
    {
        ans=ans+(n-sa[i])-lcp[i];
    }

link to solution I have checked for large cases and it works fine.Please point out the error .Thanx :)

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
10 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

My idea is similar to yours: - result = n*(n+1)/2 — sum of all LCP.

I had one WA, because I didn't add false sign '#' to the end of the string (my implementation requires that).

Here, you got my code. Suffix array is in O(nlogn) — in most of the time O(nlog^2n) is enough, but I encountered one problem where I got TLE because of it, so I made new faster one :) Feel free to use it.

http://ideone.com/6zlXeV

I don't get your idea. What is length(substring) — lcp(substring)?

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

ans=ans+(n-sa[i])-lcp[i]; — lcp[n-1] is undefined

→ Reply