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

Question

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.

Concatinate the string s1 with itself, and then use KMP algorithm on it for pattern matching to search for s2 in s1 + s1. KMP is O(n) in worst case. — Maaddy, Jul 28 '20 at 08:24

Adam.Er8 · Accepted Answer · 2020-07-28T08:12:49.120

6

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:

(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.

edited Jul 28 '20 at 08:12

answered Jul 28 '20 at 07:51

Adam.Er8

12,675
3
26
38

1

Doubling the length of the string doesn't make it non-linear, and from there it depends on the string matching algorithm that `find` uses. there are definitely ones that take linear time, lemme try and look for a source – Adam.Er8 Jul 28 '20 at 07:56
Ohh... I have also think about doubling and searching... But I am not aware of any linear time matching algorithm. – Yash Shah Jul 28 '20 at 07:58
1

@YashShah you seem to be right, based on this answer: https://stackoverflow.com/a/35220792/5052365, it's linear only on average case, but has non-linear worst case, will add this note to my answer – Adam.Er8 Jul 28 '20 at 08:01
2

There are linear algorithms according to [this wiki page](https://en.wikipedia.org/wiki/String-searching_algorithm#Basic_classification_of_search_algorithms) – Koen G. Jul 28 '20 at 08:10

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

1 Answers1