python - Python中字符串的“in”函数的时间复杂度是多少？

Question

如果我试图在 Python 中的 A 中查找字符串 B，我试图找出时间复杂度是多少？我了解列表/字典等的不同。我也知道列表的 O(n)。那么字符串也一样吗？复杂度会是 O(len(b)*len(A) 吗？

这是我正在处理的问题： 问题：给定两个字符串 A 和 B，找到 A 必须重复的最小次数，使得 B 是它的子字符串。如果没有这样的解决方案，返回-1。

比如A = "abcd" and B = "cdabcdab"，返回3，因为A重复3次（“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

标签： pythontime-complexity