@Lucifier : Hey the equation you made is not what as mine :). here it is..
at each point we are doing comparisons from middle the complexity is O(n) and we are doing the same for left and right half so the complexity is 2T(n/2). So equation becomes T(n) = 2T(n/2) + O(n) according to masters theorem the time complexity is O(n * log n). On Thu, Dec 29, 2011 at 10:08 AM, Lucifer <[email protected]> wrote: > @atul > The example that u have taken, is it correct ? > I see that in the search string 'abcdtrwdcba' acc to u the even length > palindrome is abcddcba.. > > On Dec 29, 9:23 am, atul anand <[email protected]> wrote: > > @Lucifier : > > > > this is wat i was trying to say :- > > > > string = abcdtrwdcba > > > > find even length substring and hash them , moving from left to right. > > > > hash(abcdtrwdcba) // corner case > > hash(ab) > > hash(abcd) > > hash(abcdtr) > > . > > . > > . > > hash(dcba). > > > > after hashing is done. > > > > again hash moving from right to left. > > hash(abcd) ---> hash alreday present so ...even length palindrome exists. > > you need to take care of cases like for ab ->hash is present , but is > part > > of bigger substring (abcd) when moving from right to left. so keep track > of > > the index. > > here how to keep track:- > > > > when you find hash of (ab) index=i; > > when you find second even palindrome hash(abcd). > > > > if length("abcd") > length("ab"); > > { > > temp_index=current_index + lenght("ab"); > > if(temp_index== index) > > { > > // we know ab is the part of bigger string > abcd.update > > the new even palindrome found. > > } > > > > > > > > > > > > > > > > } > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Thanks and Regards, Sumit Mahamuni. -- Slow code that scales better can be faster than fast code that doesn't scale! -- Tough times never lasts, but tough people do. -- I love deadlines. I like the whooshing sound they make as they fly by. - D. Adams -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
