-1

问题 - 编写一个名为 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

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

4

2 回答 2

1

Aho-Corasick 算法将在一个文档中以线性时间搜索多个搜索词。它的工作原理是根据搜索词构建一个有限状态自动机，然后通过该自动机运行文档。

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

因此，如果您正在搜索 ["cat", "dog", "boy", "girl"]，您可能会得到如下信息：

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

所以你知道范围的结尾是 226，向后搜索你会找到所有四个术语，最后一个是位置 50 处的“猫”。

于 2015-08-31T13:04:59.473 回答
1

start一种解决方案是使用两个索引 (和)遍历文档stop。您只需跟踪 和 之间的每一个有searchTerms多少。如果不是全部都存在，则增加直到它们存在（或到达文档末尾）。当所有人都在场时，你会增加，直到所有人都不再在场。每当所有人都在场时，您会检查该候选人是否比以前的候选人更好。这应该能够及时完成（使用有限数量的搜索词或搜索词放在一个带有查找的集合中）。就像是：startstopstopstartsearchTermssearchTermsO(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
于 2015-08-31T05:37:59.370 回答