How to find the minimum possible cycle shift to take from s1 to s2?

user_7200745 0
Viewed 280

If I have 2 strings s1 and s2, where the s2 is a cyclically shifted string of the s1. It needs to find the minimum possible cycle shift to take from s1 to s2.

Let me show an example:

s1 = 'I love cookies '

s2 = 'cookies I love ' Here the answer is 7.

It is preferable to take in linear time. There is my failed trials:

def find_minimum_cyclic_shift(s1, s2):

        if len(s1) != len(s2):
            return -1

        index = s2.index(s1[0])
        if (index > -1):
            if (s1==s2):
                return 0;

            #finalPosition = len(s2) - index
            #print(finalPosition, " index=",index)
            #return s2[0] == s1[finalPosition] and s1[finalPosition::]==s2[0:index]
        return index

But it doesn't work for the case: absabsabsf and absfabsabs. Instead of 4 I have 0. because index function returns me only the first appearing of a letter.

Please, give me at least a logic to code it.

string-matching algorithm python string
1 Answers

You can simply use find on a doubled-string, like this:

s1 = 'I love cookies '
s2 = 'cookies I love '

answer = min((s1*2).find(s2), (s2*2).find(s1))
print(answer)

Output:

7

(will print -1 if s2 is not a cyclic shift of s1).

The reason it works is that if s2 is indeed a cyclic shift of s1, then concatenating s1 to itself will contain s2 somewhere in the middle.

Luckily, this "somewhere" is exactly the size of the shift required (the number of chars in s1 that appear before s2's first char).

We also need to check the "other direction" for a possibly shorter shift, so we take the minimum result from both possible directions (could technically use arithmetic to avoid the second search, if the result is > n/2 then the answer is simply n - the result.

Note on runtime complexity: my solution does NOT guarantee a linear time, based on this answer, it can take O(N*N) in the worst case.

user_50523650
Related