поиск списка в другом списке с использованием Python

Question

Я пытаюсь написать алгоритм поиска по списку, используя Python.

Для справки: https://www.geeksforgeeks.org/sublist-search-search-a-linked-list-in-another-list/

Вот мой код:

def sublist(arr1,arr2):
i = 0
j = 0
k = 0
if len(arr1) == 0:
    print('List1 Empty')
if len(arr2) == 0:
    print('List 2 Empty')
for j in range(0,len(arr2)):
    for i in range(0,len(arr1)):
        if arr1[i] != arr2[j]:
            break
        while arr1[i] == arr2 [j]:
            if i == len(arr1) - 1:
                return True
            i = i + 1
            j = j + 1
            if i == len(arr1):
                return False
        return False 

Я уверенэтот код может быть оптимизирован и уменьшить временную сложность.Из-за цикла while сложность увеличивается, чем O (m * n)?Начинающий ученик здесь

Answer 1

Далее сравнивается первая часть от arr2 до arr1, чтобы определить, равны ли они. Если это так или любой рекурсивный вызов с некоторым смещением arr2 вернет true, тогда верните true. В противном случае, если в какой-то момент подсписок оригинала arr2 короче arr1, верните False.

def sublist(arr1, arr2):
    if len(arr2) < len(arr1):
        return False
    return arr1 == arr2[:len(arr1)] or sublist(arr1, arr2[1:])

Answer 2

Я думаю, что это работает лучше:

def sublist(arr1,arr2):
  "This fuction checks if arr1 is a sublist of arr2."
  for i in range(len(arr2)):
    part=arr2[i:] # part is a list which all the elements from i to the end of arr2
    if len(part)<len(arr1):
      return False
    if arr1==part[:len(arr1)]: # if arr1 is in the beginning of part return True
      return True
  return False