Hi Anupama
On Nov 28, 4:23 pm, "Anupama Murthi" <[EMAIL PROTECTED]> 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. Superficially this looks a quite trivial but it is a subproblem of: Is a sequence S a linear or cyclic subsequence of a sequence T which is longer, the same length or maybe shorter that S. i.e is CAC a valid cyclic subsequence of CCUCACCG, CGGCCUCA, CA. Maybe yes in all cases. As usual it is best to break the problem into separate tasks: 1) scan the sequence from 1..n, calling a function CheckCyclic(SubSequence, Sequence, Index, *FailedAt)->Boolean; 3) CheckCyclic treats the sequence as circular and checks for valid subsequences that may wrap past the end. Complexity is n*m where m is the length of subsequences. Efficiency can be improved by making CheckCyclic return items checked and start the scan again from that point. However, to do this safely we need to check the location of any leading subsequences of S within S before starting. e.g. the leading subsequence CAC occures at 4 and 7 in CACCACCAC. (C, CA at 4, 7 are already covered and C at 3, 9 do not signify) Doing this check gets a rule that must be applied to the FailedAt count returned by CheckCyclic. It is quite messy to program modifyable rules. Could to use an array. We are only going to build this once so I would make it a lookup table indexed by FailedAt holding the values to be added to the scanning Index, in the example: 1,2,3,4,4,6,7,7,9, I think. Rules to derive the rule look prety tough. Any suggestions? For the original problem first check that S and T have the same length and return False otherwise. - Martin --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
