Check if a string is rotation of another WITHOUT concatenating

Question

There are 2 strings , how can we check if one is a rotated version of another ?

For Example : hello --- lohel

One simple solution is by concatenating first string with itself and checking if the other one is a substring of the concatenated version.

Is there any other solution to it ?

I was wondering if we could use circular linked list maybe ? But I am not able to arrive at the solution.

Answer 1

One simple solution is by concatenating them and checking if the other one is a substring of the concatenated version.

I assume you mean concatenate the first string with itself, then check if the other one is a substring of that concatenation.

That will work, and in fact can be done without any concatenation at all. Just use any string searching algorithm to search for the second string in the first, and when you reach the end, loop back to the beginning.

For instance, using Boyer-Moore the overall algorithm would be O(n).

Answer 2

Trivial O(min(n,m)^2) algorithm: (n - length of S1, m - length of S2)

isRotated(S1 , S2):

if (S1.length != S2.length)
    return false
for i : 0 to n-1
    res = true
    index = i
    for j : 0 to n-1
       if S1[j] != S2[index]
           res = false
           break
       index = (index+1)%n
    if res == true
        return true
return false

EDIT:

Explanation -

Two strings S1 and S2 of lengths m and n respectively are cyclic identical if and only if m == n and exist index 0 <= j <= n-1 such S1 = S[j]S[j+1]...S[n-1]S[0]...S[j-1].

So in the above algorithm we check if the length is equal and if exist such an index.

Answer 3

You can do it in O(n) time and O(1) space:

def is_rot(u, v):
    n, i, j = len(u), 0, 0
    if n != len(v):
        return False
    while i < n and j < n:
        k = 1
        while k <= n and u[(i + k) % n] == v[(j + k) % n]:
            k += 1
        if k > n:
            return True
        if u[(i + k) % n] > v[(j + k) % n]:
            i += k
        else:
            j += k
    return False

See my answer here for more details.