concatenate 2 strings adding wild character in between i.e A="aaa" B="aaab" A+B ="aaa$aaab"; wild character is "$";
now create longest prefix table(partial match table) .... as we do in KMP algo. now search for max value after "$" index...in LPS table. I guess it would work On Sun, Aug 19, 2012 at 8:23 PM, Carl Barton <odysseus.ulys...@gmail.com>wrote: > 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. > -- 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.
