Googmeister, yours is the optimal solution...i have a trivial question here...whats the first trivial match that needs to be ignored...
suppose P= abcd and S=bcda the concatenated string is 'abcdabcd'...here the first match is the one that we need to check for...and it obviously shd not be ignored...am i missin something here.. thanks Googmeister wrote: > 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 -~----------~----~----~----~------~----~------~--~---
