That's great. It's fast, and reduces the number of searches.
Keith - CDI
// ----------------------------------------------------
// Method: Suffix_Tree - from Wiki examples
// -
// INPUT1: Text - to compare
// INPUT2: Text - to compare
// INPUT3: Pointer - array of longest matches
// OUTPUT: Longint - length
// ----------------------------------------------------
C_LONGINT($i;$size;$longest;$0)
C_TEXT($longer;$shorter;$temp)
$str1:=$1
$str2:=$2
If (Length($str1)>Length($str2))
$longer:=$str1
$shorter:=$str2
Else
$longer:=$str2
$shorter:=$str1
End if
$m:=Length($longer) // is the longer string
$n:=Length($shorter)
ARRAY LONGINT($LCSub;$m;$n)
$longest:=0
For ($i;1;$m)
For ($j;1;$n)
If ($i=1) | ($j=1)
$LCSub{$i}{$j}:=0
Else
If ($longer[[$i-1]]=$shorter[[$j-1]])
$LCSub{$i}{$j}:=$LCSub{$i-1}{$j-1}+1
If ($longest<$LCSub{$i}{$j})
$longest:=$LCSub{$i}{$j}
End if
Else
$LCSub{$i}{$j}:=0
End if
End if
End for
End for
// search for matches of $longest length
ARRAY TEXT($aMatch;0)
$size:=Length($shorter)-$longest+1
For ($i;1;$size)
$temp:=Substring($shorter;$i;$longest)
If (Position($temp;$longer;*)>1)
If (Find in array($aMatch;$temp)=-1)
APPEND TO ARRAY($aMatch;$temp)
End if
End if
End for
COPY ARRAY($aMatch;$3->)
$0:=$longest
> On Aug 24, 2019, at 2:41 PM, John DeSoi via 4D_Tech <[email protected]>
> wrote:
>
> See
>
> https://en.wikipedia.org/wiki/Longest_common_substring_problem
>
> John DeSoi, Ph.D.
>
>
>> On Aug 24, 2019, at 10:48 AM, Keith Culotta via 4D_Tech
>> <[email protected]> wrote:
>>
>> This version stands alone, and runs a little more efficiently. It's not
>> been tested in every way, but the results are encouraging. Interesting
>> problem. I can't think of a way to do it without comparing every character
>> combination. The new "Split string" command would speed part of this up if
>> Collections could be used.
>
**********************************************************************
4D Internet Users Group (4D iNUG)
Archive: http://lists.4d.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub: mailto:[email protected]
**********************************************************************
