re to find longest matching postfix of two strings

Question

I have two strings like:

a = '54515923333558964'
b = '48596478923333558964'

Now the longest postfix match is

c = '923333558964'

what will be a solution using re?

Here is a solution I found for prefix match:

import re
pattern = re.compile("(?P<mt>\S*)\S*\s+(?P=mt)")
a = '923333221486456'
b = '923333221486234567'
c = pattern.match(a + ' ' + b).group('mt')

Answer 1

You can use this variation of the regex pattern:

\S*?(?P<mt>\S*)\s+\S*(?P=mt)$

EDIT. Note, however, that this may require O(n³) time with some inputs. Try e.g.

a = 1000 * 'a'
b = 1000 * 'a' + 'b'

This takes one second to process on my system.

Answer 2

Try the difflib.SequenceMatcher:

import difflib
a = '54515923333558964'
b = '48596478923333558964'

s = difflib.SequenceMatcher(None, a, b)
m = s.find_longest_match(0, len(a), 0, len(b))
print a[m.a:m.a+m.size]