Какова сложность времени для функции "in" в Python для STRINGS? - PullRequest
Новая
       6

Какова сложность времени для функции "in" в Python для STRINGS?

0 голосов
/ 12 февраля 2019

Я пытаюсь выяснить, какова будет временная сложность, если я пытаюсь найти строку B в A в Python?Я понимаю, что он отличается для списков / словарей и т. Д. Я также знаю его O (n) для списков.так ли это для строки?Будет ли сложность O (len (b) * len (A)?

Вот проблема, над которой я работаю: Вопрос: Учитывая две строки A и B, найдите минимальное число раз, когда A должно бытьповторяется так, что B является его подстрокой. Если такого решения нет, верните -1. ​​

Например, с A = "abcd" и B = "cdabcdab", верните 3, потому что, повторяя Aтри раза («abcdabcdabcd»), B является его подстрокой, а B не является подстрокой A, повторяемой два раза («abcdabcd»).

Мой код в Python выглядит следующим образом: 

if B in A:
    return 1        

lenB=len(B)
lenA=len(A)
n=lenB+lenA
output=''

while n>1:
    output+=A
    n-=lenA


if B in output[:len(output)-lenA]:
    return (len(output)-lenA)/lenA
elif B in output:
    return len(output)/lenA
else:
    return -1
...