From: Sergey Volkov <gm.vlkv@...>
Date: 2008-01-22T19:20:20+09:00
Subject: Re: [QUIZ] Longest Repeated Substring (#153)

------=_NextPart_000_0A4D_01C85CB6.7BC09100
Content-Type: text/plain;
	format=flowed;
	charset="UTF-8";
	reply-type=original
Content-Transfer-Encoding: 7bit

Suffix tree is brilliant method, but has been invented long time ago,
besides, others submitted 'suffix tree' solution already.
It was challenge!

Please take a look at my solution (attached),
in my experiments it's faster than Eric's code.

BRs
Sergey Volkov

--------------------------------------------------------------
# Times
[vsv@gx Q153]$ ruby -v
ruby 1.8.6 (2007-03-13 patchlevel 0) [i686-linux]

### Eric's code
[vsv@gx Q153]$ time ruby Q153_EricI.rb <homer-illiad.txt
" who are
perishing and coming to a bad end. We will, however, since you so
bid us, refrain from actual fighting, but we will make serviceable
suggestions to the Argives" (168 characters)

real    0m14.263s
user    0m14.185s
sys     0m0.076s

### My solution
[vsv@gx Q153]$ time ruby Q153_SerVo.rb <homer-illiad.txt
 who are
perishing and coming to a bad end. We will, however, since you so
bid us, refrain from actual fighting, but we will make serviceable
suggestions to the Argives
[168]

real    0m7.676s
user    0m7.456s
sys     0m0.220s

### War and Peace
[vsv@gx Q153]$ time ruby Q153_SerVo.rb <wrnpc12.txt


The Project Gutenberg Literary Archive Foundation has been
[63]

real    0m30.511s
user    0m29.546s
sys     0m0.424s

### Bonus feature:
### With linebreaks removed from paragraph body
[vsv@gx Q153]$ time ruby Q153_SerVo.rb -t <homer-illiad.txt
 a messenger from Jove, who, though he be not near, yet takes thought for 
you and pities you. He bids you get the Achaeans instantly under arms, for 
you shall take Troy. There are no longer divided counsels among the gods; 
Juno has brought them over to her own mind, and woe betides the Trojans at 
the hands of Jove. Remember this
[330]

real    0m14.672s
user    0m14.129s
sys     0m0.544s
------------------------------------------------------------ 

------=_NextPart_000_0A4D_01C85CB6.7BC09100
Content-Type: application/octet-stream;
	name="Q153_SerVo.rb"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="Q153_SerVo.rb"

#!/bin/env ruby=0A=
=0A=
## Quiz 153 Solution=0A=
## Print max repeated non-overlaping substring from STDIN or nothing.=0A=
## Not suffix tree! Less memory! Very fast!=0A=
## Enjoy,=0A=
## Sergey=0A=
=0A=
##=0A=
# Usage: Q153_SerVo.rb {-U | [-t] [-n]}=0A=
# -U - run unit test=0A=
# Otherwise:=0A=
# reads standard input,=0A=
# replaces linebreak with space inside paragraph if -t,=0A=
# prints longest repeated substring / its length only if -n=0A=
=0A=
class String=0A=
    def longest_repeated_substring=0A=
        # repeated substring length=0A=
        clen =3D 1=0A=
        # repeated substring posistion=0A=
        cpos =3D 0=0A=
        # result=0A=
        rs =3D nil=0A=
        # two substrings after cpos=0A=
        while cpos+clen*2 <=3D self.size=0A=
            # second repeated substring posistion=0A=
            unless ipos =3D self.index( self.slice(cpos,clen), cpos+clen =
)=0A=
                # try next position, same length=0A=
                cpos+=3D1=0A=
                next=0A=
            end=0A=
            # extend repeated substring=0A=
            begin=0A=
                clen +=3D 1 while cpos+clen<ipos &&=0A=
                                (c =3D self[ipos+clen]) &&=0A=
                                c =3D=3D self[cpos+clen]=0A=
            end while ipos=3Dself.index(self.slice(cpos,clen), ipos+clen)=0A=
            # save repeated string=0A=
            rs =3D self.slice(cpos,clen)=0A=
            # try longer substring=0A=
            clen +=3D 1=0A=
            # find next position of repeated substring of length clen=0A=
            ncpos =3D nil=0A=
            ht =3D Hash.new=0A=
            # search for repeated substring=0A=
            for i in cpos..self.size-clen=0A=
                # current substring=0A=
                cs=3Dself.slice(i,clen)=0A=
                # seen this substring before?=0A=
                if prev_pos=3Dht[cs]=0A=
                    # check overlap=0A=
                    next if prev_pos+clen>i=0A=
                    # repeated substring found=0A=
                    ncpos =3D prev_pos=0A=
                    break=0A=
                end=0A=
                # store substring=0A=
                ht[cs]=3Di=0A=
            end=0A=
            break unless ncpos=0A=
            cpos=3Dncpos=0A=
        end=0A=
        rs=0A=
    end=0A=
end=0A=
=0A=
if __FILE__ =3D=3D $0=0A=
    if ARGV.first =3D=3D '-U'=0A=
        ARGV.shift=0A=
        require 'test/unit'=0A=
        class TC_LRS < Test::Unit::TestCase=0A=
            def test_lrs=0A=
                assert_same  nil, ''.longest_repeated_substring=0A=
=0A=
                d=3D'1234567890'=0A=
                dx =3D (1..9).inject(d){|r,i|r+'.'+r[0,i]}+'.'+d=0A=
#1234567890.1.12.123.1234.12345.123456.1234567.12345678.123456789.1234567=
890=0A=
=0A=
                assert_same  nil, d.longest_repeated_substring=0A=
                assert_equal d, (d+d).longest_repeated_substring=0A=
                assert_equal d, (d+'.'+d).longest_repeated_substring=0A=
                assert_equal d, dx.longest_repeated_substring=0A=
=0A=
                a=3Dd.gsub( /\d/, 'A' )=0A=
                ax =3D dx.gsub( /\d/, 'A' )=0A=
#AAAAAAAAAA.A.AA.AAA.AAAA.AAAAA.AAAAAA.AAAAAAA.AAAAAAAA.AAAAAAAAA.AAAAAAA=
AAA=0A=
=0A=
                assert_equal a, (a+a).longest_repeated_substring=0A=
                assert_equal a, (a+'.'+a).longest_repeated_substring=0A=
                assert_not_equal a, ax.longest_repeated_substring=0A=
            end=0A=
        end=0A=
        p :TEST=0A=
        exit Test::Unit::AutoRunner.run=0A=
    end=0A=
=0A=
    ###=0A=
    # Main=0A=
    inp =3D STDIN.read=0A=
    # for 'human text' processing (-t):=0A=
    # replace '\n' inside paragraph with ' '=0A=
    inp.gsub!(/(\S)\n(\w)/m, '\1 \2') if ARGV.grep( /-.*t/ )[0]=0A=
=0A=
    if lrs =3D inp.longest_repeated_substring=0A=
        # Output string unless '-n' specified (number only)=0A=
        puts( lrs ) if ARGV.grep( /-.*n/ ).empty?=0A=
        # Output size=0A=
        p [lrs.size]=0A=
    end=0A=
end=0A=

------=_NextPart_000_0A4D_01C85CB6.7BC09100--