Some longest common substring routines

[Terry Judd]

I recently had to adapt some python routines for finding the length and
contents of the longest common substrings of two strings to Rev and thought
they might come in handy to someone else??

Anyway here they are...

The first function simply returns the length of the longest common substring

function getLCSlength str1,str2
  if (str1 = "") or (str2 = "") then return 0
  put 0 into LCSlength
  put "" into LCStable
  repeat with i = 1 to length(str1)
    repeat with j = 1 to length(str2)
      if (char i of str1) <> (char j of str2) then
        put 0 into item i of line j of LCStable
      else
        put 1 + (item i-1 of line j-1 of LCStable) into tValue
        put tValue into item i of line j of LCStable
        put max(tValue, LCSlength) into LCSlength
      end if
    end repeat
  end repeat
  return LCSlength
end getLCSlength

This next one returns the substring itself (or at least the first substring
of that length if there are more than one)

function getLCSstring str1, str2
  if (str1 = "") or (str2 = "") then return ""
  put "" into LCScontents
  put 0 into LCSlength
  put "" into LCStable
  repeat with i = 1 to length(str1)
    repeat with j = 1 to length(str2)
      if (char i of str1) <> (char j of str2) then
        put 0 into item i of line j of LCStable
      else
        put 1 + (item i-1 of line j-1 of LCStable) into tValue
        put tValue into item i of line j of LCStable
        if tValue > LCSlength then
          put char i-tValue+1 to i of str1 into LCScontents
        end if
        put max(tValue, LCSlength) into LCSlength
      end if
    end repeat
  end repeat
  return LCScontents
end getLCSstring

And this last one returns the table containing the lengths and positions of
all the substrings (you could parse this to find different substrings of
various lengths)

function getLCStable str1, str2
  if (str1 = empty) or (str2 = empty) then return empty
  put 0 into maxLength
  put "" into LCStable
  repeat with i = 1 to length(str1)
    repeat with j = 1 to length(str2)
      if (char i of str1) <> (char j of str2) then
        put 0 into item i of line j of LCStable
      else
        put 1 + (item i-1 of line j-1 of LCStable) into tValue
        put tValue into item i of line j of LCStable
      end if
    end repeat
  end repeat
  return LCStable
end getLCStable

Cheers,

Terry...

-- 
Dr Terry Judd
Lecturer in Educational Technology (Design)
Biomedical Multimedia Unit
Faculty of Medicine, Dentistry & Health Sciences
The University of Melbourne
Parkville VIC 3052
AUSTRALIA

61-3 8344 0187