Arun wrote: > searching first copy of S in double-sized string is O(n^2). isnt it?
There are a number of linear time string searching algorithm, e.g., Knuth-Morris-Pratt. It's O(n) if you use one of these. > On 7/11/06, Googmeister <[EMAIL PROTECTED]> wrote: > > > > > > > > Terry wrote: > > > Hi, > > > > > > Say i have a string abcd > > > bcda is a cyclic permutation of abcd obtained by rotating the string 1 > > > left. > > > > > > Given a string P of length n, > > > how to determine if string S of length is cyclic permutation of string > > > P. > > > > Here's a linear time solution: concatenate two copies of the > > the original string P; then search for the first copy of S in > > the double-size string, skipping the first (trivial) match. > > > > > > > > > > > ------=_Part_3703_14181076.1152642421734 > Content-Type: text/html; charset=ISO-8859-1 > X-Google-AttachSize: 892 > > searching first copy of S in double-sized string is O(n^2). isnt > it?<br><br><div><span class="gmail_quote">On 7/11/06, <b > class="gmail_sendername">Googmeister</b> <<a href="mailto:[EMAIL > PROTECTED]">[EMAIL PROTECTED] > </a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px > solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: > 1ex;"><br><br>Terry wrote:<br>> Hi,<br>><br>> Say i have a string > abcd > <br>> bcda is a cyclic permutation of abcd obtained by rotating the string > 1<br>> left.<br>><br>> Given a string P of length n,<br>> how to > determine if string S of length is cyclic permutation of string<br> > > P.<br><br>Here's a linear time solution: concatenate two copies of > the<br>the original string P; then search for the first copy of S in<br>the > double-size string, skipping the first (trivial) match.<br><br><br> > ------=_Part_3703_14181076.1152642421734-- --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
