python - 高效查找最长匹配前缀字符串

Question

我当前的实现是这样的:

def find_longest_matching_option(option, options):
    options = sorted(options, key=len)
    longest_matching_option = None
    for valid_option in options:
        # Don't want to treat "oreo" as matching "o",
        # match only if it's "o reo"
        if re.match(ur"^{}\s+".format(valid_option), option.strip()):
            longest_matching_option = valid_option
    return longest_matching_option

我正在尝试做的一些例子:

"foo bar baz something", ["foo", "foo bar", "foo bar baz"]
# -> "foo bar baz"
"foo bar bazsomething", (same as above)
# -> "foo bar"
"hello world", ["hello", "something_else"]
# -> "hello"
"a b", ["a", "a b"]
# -> "a b" # Doesn't work in current impl.

大多数情况下，我在这里寻求的是效率。当前的实现是有效的，但我被告知它的时间复杂度为O(m^2 * n)，这非常糟糕。

提前致谢!

Answer 1

让我们从 foo 开始。

def foo(x, y):
    x, y = x.strip(), y.strip()
    return x == y or x.startswith(y + " ")

如果两个字符串相等，或者一个字符串(加一个空格)是另一个字符串的子字符串，则

foo 返回 true。

接下来，给定一个 case 字符串和一个选项列表，您可以使用 filter 查找给定 case 字符串的所有有效子字符串，然后将 max 应用到找到最长的一个(参见下面的测试)。

这里有一些 foo 的测试用例。出于演示目的，我将使用 partial 将 foo 柯里化(Currying)为高阶函数。

from functools import partial

cases = ["foo bar baz something", "foo bar bazsomething", "hello world", "a b", "a b"]
options = [
      ["foo", "foo bar", "foo bar baz"], 
      ["foo", "foo bar", "foo bar baz"],
      ["hello", "something_else"],
      ["a", "a b"],
      ["a", "a b\t"]
]
p_list = [partial(foo, c) for c in cases]

for p, o in zip(p_list, options):
    print(max(filter(p, o), key=len))

foo bar baz
foo bar
hello
a b
a b