降低此程序的时间复杂度

Question

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

如果有人想克隆我的程序，这里是代码

Answer 1

一种解决方案是使用两个索引(start 和 stop (遍历文档。您只需跟踪每个searchTerms中有多少在start和stop之间。如果不是全部都存在，则增加stop直到它们存在(或到达文档末尾(。当所有searchTerms都存在时，您会增加start直到所有都不再存在之前。每当所有searchTerms都在场时，您都会检查该候选人是否比以前的候选人更好。这应该能够在O(N)时间内完成(搜索词数量有限，或者搜索词放在一个具有O(1)查找的集合中(。像这样：

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 算法将在线性时间内在文档中搜索多个搜索词。它的工作原理是从搜索词构建一个有限状态自动机，然后通过该自动机运行文档。

因此，建立FSA并开始搜索。找到搜索词后，将它们存储在元组数组(搜索词、位置(中。找到所有搜索字词后，请停止搜索。列表中的最后一项将包含找到的最后一个搜索词。这为您提供了范围的结束位置。然后在找到的术语列表中向后搜索，直到找到所有术语。

因此，如果您正在搜索["猫"，"狗"，"男孩"，"女孩"]，您可能会得到类似以下内容：

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

所以你知道范围的尽头是 226，向后搜索你会发现所有四个项，最后一个是位置 50 的"猫"。