Longest common substring

No Language here - just algorithms!
Previous topicNext topic

Topic Author
enrico-sorichetti
Global Moderator
Global Moderator
Posts: 887
Joined: Wed Sep 11, 2013 3:57 pm

Longest common substring

Post by enrico-sorichetti » Thu Jun 25, 2015 7:43 pm

Open Object Rexx only
http://www.oorexx.org
http://www.oorexx.org/download.html

Code: Select all

#!  /usr/bin/rexx
Trace "O"
signal on novalue name novalue

say ">>"LCS("abc", "xabcy")"<<"
say ">>"LCS("abc", "def")"<<"
say ">>"LCS("mABnCDo", "xAByCDz")"<<"
say ">>"LCS("mABnCDo", "xAByCDz", "L")"<<"

exit

/*  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
LCS:procedure
    use strict arg  s, t, f="F"

    if  translate(f) = "F" then ,
        f = 1
    else ,
        f = 0

    m   = s~length()
    n   = t~length()

    k   = 0
    L   = .array~new()

    r = ""

    do  i = 1 to m
        do  j = 1 to n

            if substr(s,i,1) = substr(t,j,1) then do
                if  ( ( i = 1 ) | (j = 1) ) then ,
                    L[i,j] = 1
                else ,
                    L[i,j] = L[i-1,j-1] + 1
                if  f = 1 then do
                    /*  first match
                    */
                    if  L[i,j] > k then do
                        k = L[i,j]
                        r = substr(s,i-k+1,k)
                    end
                end
                else do
                    /*  last match
                    */
                    if  L[i,j] >= k then do
                        k = L[i,j]
                        r = substr(s,i-k+1,k)
                    end
                end
            end
            else do
                L[i,j] = 0
            end

        end /* do  i = 1 to m */
    end /* do  j = 1 to n */

    return r

/*  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
logic_error:
say "**"copies(" -", 35)
say "**"
say "**" "Logic error at line '"sigl"' "
say "**"
say "**"copies(" -", 35)
exit

/*  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
novalue:
say "**"copies(" -", 35)
say "**"
say "**" "Novalue trapped, line '"sigl"' var '"condition("D")"' "
say "**"
say "**"copies(" -", 35)
exit


cheers
enrico
When I tell somebody to RTFM or STFW I usually have the page open in another tab/window of my browser,
so that I am sure that the information requested can be reached with a very small effort 8-)

Previous topicNext topic

Return to “Programming Algorithms.”