Определите, содержит ли строка, содержащуюся в другой строке, в python

Question

Я ищу, чтобы определить, содержится ли строка в начале списка другой строки. Например, если я имел строку cde, и список строк:

['ab', 'bce', 'cdef'] 

тогда будет определять, что cde содержится в начале cdef

Я также ищу пойти в другую сторону вокруг - то есть, если бы у меня был термин abc, чтобы определить, что ab из вышеуказанного списка содержится в нем.

Теперь очевидно, что это тривиально, чтобы настроить цикл for, проверяя каждый экземпляр с помощью функции startswith, однако это не масштабируется с очень большим списком возможностей для проверки.

При проверке каждого экземпляра O (n) [и, следовательно, очень медленного, если у вас есть 100 000 возможностей], я ищу способ проверки O (1) ... похоже, что если «список» был предварительно отсортированный, тогда можно просто извлечь ближайшее совпадение, но не уверен, как это сделать.

Разъяснение:

• Я только ищу, где есть идеальный матч в начале строки (то есть весь срок поиска включен).
• Я буду искать несколько поисковых терминов (таким образом, при первоначальной сортировке данные могут быть не быстрыми, стоимость потолка будет экономить на последующих смотровых прогибах).
• Идеально возвратит все возможные соответствия (т. Е. Если cdef и cdefg, где в списке, и глядя вверх cde, тогда оба будут возвращены).
• Я использую термин «список» свободно, как в наборе терминов.

Answer 1

Это не представляется возможным в O (1), так как, по определению, вы должны пройти через весь массив. Если массив отсортирован, вы можете выполнить двоичный поиск для своей строки, а затем проверить, начинается ли элемент в этой позиции с вашей строки. Эта операция O (log n).

import bisect 

# return the index of the string starting with the prefix 
# or None if no such string is in the list 
def search(a, prefix): 
    i = bisect.bisect_left(a, prefix) 
    isAtStart = (i < len(a) and a[i].startswith(prefix)) 
    return i if isAtStart else None 

search(['ab', 'bce', 'cdef'], 'bc')