Входные данные для поиска по подстроке Python - PullRequest
Новая
       17

Входные данные для поиска по подстроке Python

0 голосов
/ 25 июня 2019

Реализация поиска подстроки в CPython (например, через in) реализована с помощью следующего алгоритма. 

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

По крайней мере, согласно этому источнику (взято из этот старый ответ ), написанный автором (?) реализации CPython.

Этот же источник упоминает сложность этого алгоритма в наихудшем случае как O(nm), где n и m - длины двух строк.Меня интересует, является ли эта граница жесткой.Мой вопрос:

Существуют ли альтернативные примеры для алгоритма, используемого в Python in?Можем ли мы дать последовательность пар строк (pattern, string), чтобы выполнение pattern in string заняло квадратичное (или хотя бы суперлинейное) время?

Стандартный пример, демонстрирующий квадратичное время выполнения наивного поиска по наихудшим случаям, где string = 'a'*n и pattern = 'a'*m + b не работают .

Ответы [ 2 ]

3 голосов
/ 28 июня 2019

Наивный пример s='a'*n и p='a'*m+'b' не работает из-за строки 

if s[i+m-1] == p[m-1]:

Это проверяет последний (не первый) символ p ('b') ссоответствующая текущая позиция в s.Поскольку это не удается, то результатом является всего лишь одна итерация по s, поэтому она так быстра.

Если вы перевернете p (s='a'*n и p='b'+'a'*m), тогдапроисходит то же самое - на этот раз вышеупомянутая строка проходит (последний символ p теперь 'a'), но затем p перебирается вперед, поэтому затем 'b' быстро обнаруживается, поэтому снова этот примерлинейный и быстрый.

Простое изменение наивного примера, которое показало бы поведение O(nm), это s='a'*n и p='a'*m+'ba'.В этом случае последний символ p равен 'a', поэтому первоначальная проверка проходит, но затем ему необходимо выполнить итерацию по оставшейся части p, прежде чем он достигнет 'b'. 

# full='a'*n; sub='a'*m+'b'
>>> timeit("sub in full", "sub='a'*10+'b'; full='a'*100")
0.13620498299860628
>>> timeit("sub in full", "sub='a'*10+'b'; full='a'*1000")
0.9594046580004942
>>> timeit("sub in full", "sub='a'*100+'b'; full='a'*1000")
0.9768632190007338
# Linear in n, but m has minimal effect: ~O(n)

# full='a'*n; sub='a'*m+'ba'
>>> timeit("sub in full", "sub='a'*10+'ba'; full='a'*100")
0.35251976200015633
>>> timeit("sub in full", "sub='a'*10+'ba'; full='a'*1000")
3.4642483099996753
>>> timeit("sub in full", "sub='a'*100+'ba'; full='a'*1000")
27.152958754999418
# Both n and m have linear effect: ~O(nm)
0 голосов
/ 26 июня 2019

Попробуйте это: 

import re
import time

def slow_match(n):
    pat = 'a' + ('z' * n)
    str = 'z' * (n + n)
    start_time = time.time()
    if re.search(pat, str):
        print("Shouldn't happen")
    print(("Searched", n, time.time() - start_time))

slow_match(10000)
slow_match(50000)
slow_match(100000)
slow_match(300000)
...