Tech Tip: Finding the longest common substring between two strings

PRODUCT: 4D | VERSION: 15.x | PLATFORM: Mac & Win

Published On: October 28, 2016

Below is an utility method to find the longest common substring between two strings.

C_TEXT($1;$s1;$2;$s2)
C_LONGINT($lens1;$lens2;$longest;$x_longest)
C_LONGINT($x;$y;$numChars;$start)
If (Count parameters>=2)
   $s1:=$1
   $s2:=$2

   $lens1:=Length($s1)
   $lens2:=Length($s2)
   ARRAY LONGINT($m;$lens1;$lens2)
   ARRAY TEXT($arr;0)
   $longest:=0
   $x_longest:=0
   For ($x;1;$lens1)
      For ($y;1;$lens2)
         If (Character code($s1[[$x]])=Character code($s2[[$y]]))
            $m{$x}{$y}:=$m{$x-1}{$y-1}+1
            If ($m{$x}{$y}>$longest)
               $longest:=$m{$x}{$y}
               $x_longest:=$x
            End if
         Else
            $m{$x}{$y}:=0
         End if
      End for
   End for

   $start:=($x_longest-$longest)+1
   $numChars:=($x_longest-$start)+1
   $0:=Substring($s1;$start;$numChars)
End if

Example:

$common:=UTIL_LONGEST_COMMON_STR("ABABC";"ABCBA")

$common = "ABC"