Compare two lists to see if one is a rotation of the other 2

Question

Second attempt to solve this rotation problem, implemented a double ended queue as was suggested in a comment of my first attempt. So did I finally do the problem some justice or is there perhaps a better solution? Also anything I can and should clean up? I wanted to thank everyone from my previous post for their help and suggestions!

'''
Attempt 2
Problem statement: Given 2 integer arrays, determine if the 2nd array is a rotated version of the 1st array. 
Ex. Original Array A={1,2,3,5,6,7,8} Rotated Array B={5,6,7,8,1,2,3} 

@author: Anonymous3.1415
'''

from collections import deque


def is_rotated(lst1, lst2):
    '''is lst2 a rotation of lst1 '''

    if len(lst1) != len(lst2):
        return False
    if lst1 == [] and lst2 == []:
        return True

    d_lst1 = deque(lst1)
    d_lst2 = deque(lst2)

    #rotate all possible rotations to find match
    for n in range(len(d_lst1)):
        d_lst2.rotate(n) 
        if d_lst2 == d_lst1:
            return True
        d_lst2.rotate(-n)
    return False

# rotation
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,7,1,2,3,4]
assert is_rotated(lst1, lst2)

# rotation with repeated numbers
lst1, lst2 = [1,2,3,4,6,4,7,1], [6,4,7,1,1,2,3,4]
assert is_rotated(lst1, lst2)

# different set
lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
assert not is_rotated(lst1, lst2)

# equal
lst2 = lst1
assert is_rotated(lst1, lst2)

# empty
lst1, lst2 = [], []
assert is_rotated(lst1, lst2)

# 1 empty, 1 not empty
lst1, lst2 = [], [1]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1], []
assert not is_rotated(lst1, lst2)

Answer 1

If you compare one of the lists with all the rotations of the other list, this will take \$\Theta(n^2)\$ in the worst case.

For example, if we make test cases like this:

from timeit import timeit
def test(n):
    l1 = [0] * n
    l2 = [0] * (n - 1) + [1]
    return timeit(lambda:is_rotated(l1, l2), number=1)

then the quadratic runtime can be clearly seen in the timings:

>>> test(10**3)
0.009426131844520569
>>> test(10**4)
0.5701698779594153
>>> test(10**5)
57.70295810396783

There are a couple of ways to solve this problem in linear time:

1. Search for one list in the concatenation of the other list with itself, using a search algorithm that has linear time in the worst case, for example Knuth–Morris–Pratt.

   Here's an illustration of this approach using strings instead of lists:

   >>> a, b = 'basketwork', 'workbasket'
   >>> a in b + b
   True
   

2. Find the lexicographically minimal rotation of each of the lists to be compared (for example using Booth's algorithm) and see if the results are the same.