python str.index時間の複雑度

Question

文字列内の部分文字列の位置を見つけるには、単純なアルゴリズムではO(n^2)の時間がかかります。しかし、いくつかの効率的なアルゴリズムを（例えばKMP algorithm）を使用して、これはO（n）の時間で達成することができます。

s = 'saurabh' 
w = 'au' 

def get_table(): 
    i = 0; j = 2 
    t = [] 
    t.append(-1); t.append(0) 
    while i < len(w): 
     if w[i] == w[j-1]: 
      t.append(j+1) 
      j += 1 
     else: 
      t.append(0) 
      j = 0 
     i += 1 
    return t 

def get_word(): 
    t = get_table() 
    i = j = 0 
    while i+j < len(s): 
     if w[j] == s[i+j]: 
      if j == len(w) - 1: 
       return i 
      j += 1 
     else: 
      if t[j] > -1: 
       i = i + j - t[j] 
       j = t[j] 
      else: 
       i += 1 
    return -1 

if __name__ == '__main__': 
    print get_word() 

しかし、私たちがしなければ：'saurabh'.index('ra')、それは内部O(n)かでこれを計算するためにいくつかの効率的なアルゴリズムを使用しませんそれは複雑さの純粋なアルゴリズムを使用しますO(n^2)？

Answer 1

そのその記事の中で、この

Python string 'in' operator implementation algorithm and time complexity

またはこの

http://effbot.org/zone/stringlib.htm

Answer 2

で数algorithms-表情の組み合わせは、[1]の著者は、そのアルゴリズムを通過し、それを説明しています。記事から：

The function “fastsearch” is called. It is a mix between 
Boyer-Moore and Horspool algorithms plus couple of neat tricks. 

そしてボイヤー - ムーアHorspoolアルゴリズムのwikiページから[2]：

The algorithm trades space for time in order to obtain an 
average-case complexity of O(N) on random text, although 
it has O(MN) in the worst case, where the length of the 
pattern is M and the length of the search string is N. 

希望に役立つこと！

[1] http://www.laurentluce.com/posts/python-string-objects-implementation

[2] https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm

Answer 3

は時にはあなただけ試みることによって迅速な答えを得ることができ

>>> timeit.timeit('x.index("ra")', setup='x="a"*100+"ra"') 
0.4658635418727499 
>>> timeit.timeit('x.index("ra")', setup='x="a"*200+"ra"') 
0.7199222409243475 
>>> timeit.timeit('x.index("ra")', setup='x="a"*300+"ra"') 
0.9555441829046458 
>>> timeit.timeit('x.index("ra")', setup='x="a"*400+"ra"') 
1.1994099491303132 
>>> timeit.timeit('x.index("ra")', setup='x="a"*500+"ra"') 
1.4850994427915793