Какова средняя и наихудшая временная сложность моего алгоритма поиска строк? ⇐ Python

[Anonymous]

Я создал этот алгоритм для возврата индекса первого появления иголки в стоге сена или -1, если иголка не является частью стога сена. Он прошел LeetCode с нижней границей, равной единице, и верхней границей, равной десяти в степени четыре, как для иглы, так и для стога сена, и люди говорили, что решения O (n * m) вообще не проходят, поэтому я предполагаю, что средняя временная сложность несколько лучше; однако я не могу сказать наверняка, поскольку временную сложность основного цикла while сложно понять.
Код:

Код: Выделить всё

def stringSearch(haystack, needle):
s = []

if len(needle) == 1:
for i,n in enumerate(haystack):
if n == needle:
return i
return -1

for i,n in enumerate(haystack):
if n == needle[0] and (len(haystack) - i) >= len(needle):
s.append(i)

new = []
for i in s:
if i + 1 < len(haystack) and haystack[i + 1] == needle[1]:
new.append((i, i + 1, 2))
if new and len(needle) == 2:
return new[0][0]

while 1:
temp = []
for first, start, check in new:
if haystack[start + 1] == needle[check]:
temp.append((first, start + 1, check + 1))
if check + 1 >= len(needle):
return first
if not temp:
return -1
new = temp
stringSearch("", "")

Наихудшим случаем, очевидно, являются случаи, когда стог сена представляет собой гигантский повторяющийся узор, и игла следует этому образцу в таких случаях, как «хахахахахахахаха» и «ха-ха» или «ааааааааааааааааа» и «аа» .

Подробнее здесь: https://stackoverflow.com/questions/782 ... ing-algori