Find the largest common part of two strings using Vim script

Question

I have two string variables. The second string is a changed version of the first. Like this:

let a = 'this is a string'
let b = 'oh this is another string'

I would like to find the largest substring that is in both.

In the example the result would be this is a.

What is the easiest way to do this in Vim, considering the variables may contain an arbitrary line of text?

My initial idea was to concat both strings

this is a string|oh this is another string

and then use matchlist() with this regex:

\v(.+).*\|.*\1

Unfortunately, the group in the parentheses just matched ' string'.

Answer 1

Try this:

function! LongestCommonSubstring(foo, bar)
  let longest = ''
  for n in range(strlen(a:foo))
    let common = matchlist(strpart(a:foo, n) . '|' . a:bar, '\v(.+).*\|.*\1')[1]
    if strlen(common) > strlen(longest)
      let longest = common
    endif
  endfor
  return longest
endfun

For long strings, it is probably less efficient than the algorithms in @Jeff's link, but it handles this is a string and oh this is another string fine.

The longest line is exactly 80 characters, so by the usual standards it is OK, but it is dense enough that it might be clearer to split it up:

    let pasted = strpart(a:foo, n) . '|' . a:bar
    let common = matchlist(pasted, '\v(.+).*\|.*\1')[1]

or perhaps

    let common = matchstr(pasted, '\v\zs(.+)\ze.*\|.*\1')

Of course, this only works if | is not in either string.