Find longest match string from python list

Question

Let suppose we have a list i python of 35000 values like:

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

and string to match:

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

Now I want to match these strings to list to find longest match. result for first string will be 25896 while second match will return 2589 and finally last string will failed to match.

I have used regular expression to solve this issue but it's taking long as I have around 50 sets of list and around 200 strings to match each list.

here is my code:

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

Any help will be appreciated.

score 5 · Accepted Answer · answered Aug 11 '12 at 09:55

5

You can build a trie from the lists. Then you should be able to find the longest match very quickly

enter image description here

answered Aug 11 '12 at 09:55

John La Rooy

295,403
53
369
502

Related question: https://stackoverflow.com/a/11016430/1548275 – Jari Turkia Dec 11 '22 at 21:06

score 2 · Answer 2 · answered Aug 11 '12 at 08:50

2

Why not sort the list into descending order and then the first match will be the longest. This way you don't have to run each iteration to completion.

answered Aug 11 '12 at 08:50

JamesSwift

863
1
7
16

1

Even better if you build a pattern with them as alternatives, sorted in reverse order by length. – MRAB Aug 11 '12 at 19:50

Find longest match string from python list

2 Answers2