You are given two strings S and T , each n characters long. You have to establis

Question

You are given two strings S and T , each n characters long. You have to establish whether one of them is a right cyclic shift of the other. For example, PLEA is a right cyclic shift of LEAP, and vice versa. (Formally, T is a right cyclic shift of S if T can be obtained by concatenating the (n ? i)-character suffix of S and the i-character prefix of S for some 1? i ? n.)

a. Design a space-efficient algorithm for the task. Indicate the space and time efficiencies of your algorithm.
b. Design a time-efficient algorithm for the task. Indicate the time and space efficiencies of your algorithm.

Explanation / Answer

a) Rotate the string S for n -> 1 to n.
Compare every rotation to T, if found then return true
If no match for n -> 1 to n, then return false;

Space complexity: No extra variables are used, only given strings are compared.
Time complexity : O(n)

b)
Double the string S, i.e S1 = PLEAPLEA
Now find T in S1

Space complexity : S1 is used and space complexity is more than a)
Time complexity : Less than O(n)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.