Anupama Murthi wrote:
> Hi all,
> linear time to determine cyclic strings... give a linear time algorithm to
> determine if a text T is a cyclic rotation of another string T'. For eg. ARC
> and CAR are cyclic rotations of each other.
>
> --
> Anupama
could i add in my 2 cents?if i am being stupid, you guys could kick
me :P
instead of checking each time whether the string is equal or not (as
in at each position inside the BigString), do it this way instead-
ARCDARCDARCD
A+R+C
start from the first letter in the BigString, and add(ASCII) upto 3
letters(since it is CDA you need to check for; if it was CDAR, then
add 4 letters)
and as you iterate through the BigString letter by letter, subtract
the leaving letter and add the incoming letter
ARCDARCDARCD
Sum = A+R+C (Before)
Sum = A + R + C - A + D (After)
now at whatever iteration your Sum = C + D +A, that could be a
possible location for the substring CDA
this could be a slightly better method for matching a substring. but
then again, i am usually wrong!
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
