longest repeated substring ( non overlay )

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 repeated substring ( non overlay )

Post by enrico-sorichetti » Sat Jun 27, 2015 3:12 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 ">>"LRSNO("abababcabc")"<<"
say ">>"LRSNO("banana")"<<"
say ">>"LRSNO("abababab")"<<"

exit

/*  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
LRSNO:procedure

    use strict arg s

    m = s~length()

    k   = 0
    L   = .array~new

    r   = ""

    do  i = 1 to m
        do  j = i + 1 to m

            if substr(s,i,1) = substr(s,j,1) then do
                if  i = 1 then ,
                    L[i,j] = 1
                else do
                    if  j-i > L[i-1,j-1] then do
                        L[i,j]  = L[i-1,j-1] + 1
                        if  L[i,j] > k then do
                            k   = L[i,j]
                            r   = substr(s,i-k+1,k)
                        end
                    end
                    else do
                        L[i,j]  = 0
                    end
                end
            end
            else do
                L[i,j]  = 0
            end

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

    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.”