python的运行时if字符串中的子字符串

Question

以下大O是if statement什么？

if "pl" in "apple":
   ...

如果字符串"pl"在字符串"apple"中找到,python如何确定的总体大O是多少？

或字符串搜索中的任何其他子字符串.

这是测试子字符串是否在字符串中的最有效方法吗？它使用相同的算法.find()吗？

Answer 1

时间复杂度平均为O(N),O(NM)最坏情况(N是较长字符串的长度,M,您搜索的较短字符串).

同样的算法被用于str.index(),str.find(),str.__contains__()(在in运营商)和str.replace(); 这是Boyer-Moore的简化,其中包含了Boyer-Moore-Horspool和Sunday算法的想法.

查看原始的stringlib讨论帖,以及fastsearch.h源代码 ; 自从Python 2.5中引入以来,基本算法没有改变(除了一些低级优化和角落修复).

该帖子包含算法的Python代码大纲:

def find(s, p):
    # find first occurrence of p in s
    n = len(s)
    m = len(p)
    skip = delta1(p)[p[m-1]]
    i = 0
    while i <= n-m:
        if s[i+m-1] == p[m-1]: # (boyer-moore)
            # potential match
            if s[i:i+m-1] == p[:m-1]:
                return i
            if s[i+m] not in p:
                i = i + m + 1 # (sunday)
            else:
                i = i + skip # (horspool)
        else:
            # skip
            if s[i+m] not in p:
                i = i + m + 1 # (sunday)
            else:
                i = i + 1
    return -1 # not found

以及速度比较.

Answer 2

在python 3.4.2中,看起来他们正在使用相同的功能,但是时间可能会有所不同.例如,s.find首先需要查找find字符串的方法等.

使用的算法是Boyer-More和Horspool之间的混合.