python - 后缀搜索 - Python

Question

这是一个问题，提供一个字符串列表和一个文档，找到包含列表中所有字符串的最短子字符串。

因此:

document = "many google employees can program because google is a technology company that can program"
searchTerms = ['google', 'program', 'can']

输出应该是:

"can program because google"  # 27 chars

而不是:

"google employees can program"  # 29 chars
"google is a technology company that can program"  # 48 chars

这是我的方法，将文档拆分为后缀树，检查每个后缀中的所有字符串返回最短长度之一，

这是我的代码

def snippetSearch(document, searchTerms):
    doc = document.split()
    suffix_array = create_suffix_array(doc)
    current = None
    current_len = sys.maxsize
    for suffix in suffix_array:
        if check_for_terms_in_array(suffix, searchTerms):
            if len(suffix) < current_len:
                current_len = len(suffix)
                current = suffix    

    return ' '.join(map(str, current))


def create_suffix_array(document):
    suffix_array = []
    for i in range(len(document)):
        sub = document[i:]
        suffix_array.append(sub)
    return suffix_array


def check_for_terms_in_array(arr, terms):
    for term in terms:
        if term not in arr:
            return False

    return True

这是一个在线提交，没有通过一个测试用例。我不知道测试用例是什么。我的问题是，代码在逻辑上是否有任何错误。还有更有效的方法吗？

Answer 1

您可以将其分为两部分。首先，找到与某些属性匹配的最短子串。我们假设我们已经有一个测试该属性的函数:

def find_shortest_ss(document, some_property):
    # First level of looping gradually increases substring length
    for x in range(len(document)):
        # Second level of looping tests current length at valid positions
        for y in range(max(len(document), len(document)-x)):
            if some_property(document[y:x+y]):
                return document[y:x+y]
    # How to handle the case of no match is undefined
    raise ValueError('No matching value found')

现在我们要测试的属性:

def contains_all_terms(terms):
    return (lambda s: all(term in s for term in terms))

此 lambda 表达式接受一些项并将返回一个函数，当且仅当所有项都在字符串中时，该函数在对字符串求值时返回 true。这基本上是嵌套函数定义的更简洁版本，您可以这样写:

def contains_all_terms(terms):
    def string_contains_them(s):
        return all(term in s for term in terms)
    return string_contains_them

所以我们实际上只是返回我们在 contains_all_terms 函数中动态创建的函数的句柄

为了将其拼凑在一起，我们这样做:

>>> find_shortest_ss(document, contains_all_terms(searchTerms))
'program can google'

此代码具有的一些效率优势:

1. any 内置函数具有短路求值，这意味着它会在找到未包含的子字符串时立即返回 False

2. 它首先检查所有最短的子串，然后继续增加子串的长度，一次增加一个额外的字符长度。如果它找到一个令人满意的子字符串，它将退出并返回该值。所以你可以保证返回的值永远不会超过必要的长度。它甚至不会对超过必要时间的子字符串执行任何操作。

3. 8行代码，我觉得还不错