Some longest common substring routines
Terry Judd
tsj at unimelb.edu.au
Thu Apr 19 21:32:36 EDT 2007
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
More information about the use-livecode
mailing list