Сокращение временной сложности этой программы

Question

Вопрос. Напишите функцию, называемую answer (document, searchTerms), которая возвращает самый короткий фрагмент документа, содержащий все заданные условия поиска. Условия поиска могут отображаться в любом порядке.

Inputs: 
(string) document = "many google employees can program" 
(string list) searchTerms = ["google", "program"] 
Output: 
(string) "google employees can program" 

Inputs: 
(string) document = "a b c d a" 
(string list) searchTerms = ["a", "c", "d"] 
Output: 
(string) "c d a" 

Моя программа ниже дает правильный ответ, но время сложность очень высока, так как я делаю декартово произведение. Если вход очень высок, я не могу очистить эти тестовые примеры. Я не могу уменьшить сложность этой программы, и любая помощь будет принята с благодарностью. Благодаря

import itertools 

import sys 

def answer(document, searchTerms): 

    min = sys.maxint 

    matchedString = "" 

    stringList = document.split(" ") 

    d = dict() 

    for j in range(len(searchTerms)): 

     for i in range(len(stringList)): 

      if searchTerms[j] == stringList[i]: 

       d.setdefault(searchTerms[j], []).append(i) 

    for element in itertools.product(*d.values()): 

     sortedList = sorted(list(element)) 

     differenceList = [t - s for s, t in zip(sortedList, sortedList[1:])] 

     if min > sum(differenceList): 

      min = sum(differenceList) 
      sortedElement = sortedList 

      if sum(differenceList) == len(sortedElement) - 1: 
      break 

    try: 
     for i in range(sortedElement[0], sortedElement[len(sortedElement)-1]+1): 

      matchedString += "".join(stringList[i]) + " " 

    except: 
     pass 

    return matchedString 

Если кто-то хочет, чтобы клонировать мою программу здесь code

Answer 1

Одним из решений было бы перебрать документа с помощью двух индексов (start и stop). Вы просто отслеживаете, сколько из каждого из searchTerms находится между start и stop. Если не все присутствуют, вы увеличиваете stop до тех пор, пока они не (или вы не дойдете до конца документа). Когда все присутствуют, вы увеличиваете start до до того, как все searchTerms больше не будут представлены. Всякий раз, когда присутствуют все searchTerms, вы проверяете, лучше ли этот кандидат, чем предыдущие кандидаты. Это должно быть сделано в O(N) раз (с ограниченным количеством поисковых терминов или поисковыми запросами ставится набор с O(1) lookup). Что-то вроде:

start = 0 
stop = 0 
counts = dict() 
cand_start = None 
cand_end = None 

while stop < len(document): 
    if len(counts) < len(searchTerms): 
     term = document[stop] 
     if term in searchTerms: 
      if term not in counts: 
        counts[term] = 1 
      else: 
        counts[term] += 1 
    else: 
     if cand_start is None or stop-start < cand_stop-cand_start: 
      cand_start = start 
      cand_stop = stop 
     term = document[start] 
     if term in counts: 
      if counts[start] == 1: 
       del counts[start] 
      else: 
       counts[start] -= 1 
     start += 1 

Answer 2

Aho-Corasick algorithm будет искать документ для нескольких поисковых терминов в линейное время. Он работает, создавая автомат конечного состояния из поисковых терминов, а затем запуская документ через этот автомат.

Итак, создайте FSA и начните поиск. Когда поисковые запросы найдены, сохраните их в массиве кортежей (поисковый запрос, позиция). Когда вы найдете все условия поиска, остановите поиск. Последний элемент в вашем списке будет содержать последний найденный поисковый запрос. Это дает конечную позицию диапазона. Затем выполните поиск назад в этом списке найденных терминов, пока не будут найдены все термины.

Так что если вы ищете [ «кошка», «собака», «мальчик», «девочка»], вы можете получить что-то вроде:

cat - 15 
boy - 27 
cat - 50 
girl - 97 
boy - 202 
dog - 223 

Таким образом, вы знаете конец диапазона 226, и поиск в обратном порядке вы найдете все четыре термина, последний из которых является «кошкой» в позиции 50.