Search code examples
pythonregexstring-matchinglongest-substring

re to find longest matching postfix of two strings

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')
Solution

  • 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(n3) time with some inputs. Try e.g. 

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

    This takes one second to process on my system.