查找Python列表最長匹配串

Question

讓我們假設有像35000個值的列表我的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

爲什麼不按照降序對列表進行排序，然後第一個匹配將是最長的。這樣你就不必每次迭代運行完成。