Oh, I actually read the question totally wrong. I think this idea is linear, but it's late so I'm not sure.
1. Calculate suffix array and lcp array for the text. 2. Calculate the longest common prefix between your text and the first entry in your suffix array and initialise a variable called total with this value and another variable called last. Last is a variable to store the lcp between the text and the last suffix you considered. 3. Now traverse the suffix array using the lcp array. for some point, i, if the lcp between the text and the last entry is > lcp[i+1] you can do total = total + lcp[i+1] if the lcp between the text and the last entry is < lcp[i+1] you can do total = total + lcp[i-1] if the lcp between the text and the last entry is = lcp[i+1] you need to do some more work and try and extend the match from position lcp[i+1] I think that should be linear though? correctme if i'm wrong. On 19 August 2012 22:23, pankajsingh <psingh...@gmail.com> wrote: > @Carl- I didnt got ur point completely abt Lcp array..can you demonstrate > on the below example... > Example for ababaa > answer shud be -11 > suffix array wud be:- > a > aa > abaa > ababaa > baa > > and Lcp array would be then > > 0 > > 1 > 1 > 3 > 0 > ..correct if wrong..whats next... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
