-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 であることがわかり、逆方向に検索すると、4 つの用語すべてが見つかり、最後の用語は位置 50 の「cat」です。

于 2015-08-31T13:04:59.473 に答える