[algogeeks] Re: Cyclic permutation

Tue, 11 Jul 2006 11:27:03 -0700

searching first copy of S in double-sized string is O(n^2). isnt it?

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.



--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---

Reply via email to