python - 从python列表中查找最长的匹配字符串

Question

假设我们有一个包含 35000 个值的列表 i python，例如：

a = ['235', '2589', '25896']

和要匹配的字符串：

str = '258963548'
str2 = '258954213'
str3 = '258659652'

现在我想将这些字符串匹配到列表中以找到最长的匹配项。第一个字符串的结果将是 25896，而第二个匹配将返回 2589，最后一个字符串将无法匹配。

我已经使用正则表达式来解决这个问题，但它需要很长时间，因为我有大约 50 组列表和大约 200 个字符串来匹配每个列表。

这是我的代码：

def Matchit(str,b = []):
    pattern = re.compile("(?P<mt>\S*)\S*\s+(?P=mt)")
    ln = 0
    res = -1
    for a in b:
        match = pattern.match(str + ' ' + a).group('mt')
        if (len(match)>ln):
            ln = len(match)
            if(ln>2):
               res = b[a]
   return res

任何帮助将不胜感激。

Answer 1

您可以从列表中构建一个trie 。然后你应该能够很快找到最长的匹配

Answer 2

为什么不将列表按降序排序，然后第一个匹配项将是最长的。这样您就不必运行每个迭代来完成。