[QUIZ] Longest Repeated Substring (#153)

Discussion in 'Ruby' started by Ruby Quiz, Jan 18, 2008.

  1. Ruby Quiz

    Ruby Quiz Guest

    The three rules of Ruby Quiz:

    1. Please do not post any solutions or spoiler discussion for this quiz until
    48 hours have passed from the time on this message.

    2. Support Ruby Quiz by submitting ideas as often as you can:

    http://www.rubyquiz.com/

    3. Enjoy!

    Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
    on Ruby Talk follow the discussion. Please reply to the original quiz message,
    if you can.

    -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    This week's Ruby Quiz is to write a script that finds the longest repeated
    substring in a given text.

    Your program will be passed some text on STDIN and is expected to print the
    longest repeated substring within that text to STDOUT.

    Repeated substrings may not overlap. If more than one substring is repeated
    with the same length, you may print any of them. If there is no repeated
    substring, the result is an empty string (print nothing).

    Example:

    $ echo banana | ruby longest_repeated_substring.rb
    an

    OR

    $ echo banana | ruby longest_repeated_substring.rb
    na

    Make sure your code runs efficiently when passed a large text.
     
    Ruby Quiz, Jan 18, 2008
    #1
    1. Advertising

  2. Ruby Quiz

    James Gray Guest

    On Jan 18, 2008, at 7:23 AM, Ruby Quiz wrote:

    > This week's Ruby Quiz is to write a script that finds the longest
    > repeated
    > substring in a given text.


    > Make sure your code runs efficiently when passed a large text.


    Posting the strings you find in a given text and/or timings is not a
    spoiler.

    James Edward Gray II
     
    James Gray, Jan 18, 2008
    #2
    1. Advertising

  3. On 18 Jan 2008, at 13:23, Ruby Quiz wrote:
    > This week's Ruby Quiz is to write a script that finds the longest
    > repeated
    > substring in a given text.
    >
    > Your program will be passed some text on STDIN and is expected to
    > print the
    > longest repeated substring within that text to STDOUT.
    >
    > Repeated substrings may not overlap. If more than one substring is
    > repeated
    > with the same length, you may print any of them. If there is no
    > repeated
    > substring, the result is an empty string (print nothing).
    >
    > Example:
    >
    > $ echo banana | ruby longest_repeated_substring.rb
    > an
    >
    > OR
    >
    > $ echo banana | ruby longest_repeated_substring.rb
    > na
    >
    > Make sure your code runs efficiently when passed a large text.
    >


    Should white space and punctuation be treated as part of the
    substring, or are they to be ignored?

    /dh
     
    Denis Hennessy, Jan 18, 2008
    #3
  4. Ruby Quiz

    James Gray Guest

    On Jan 18, 2008, at 9:49 AM, Denis Hennessy wrote:

    > On 18 Jan 2008, at 13:23, Ruby Quiz wrote:
    >> This week's Ruby Quiz is to write a script that finds the longest
    >> repeated
    >> substring in a given text.
    >>
    >> Your program will be passed some text on STDIN and is expected to
    >> print the
    >> longest repeated substring within that text to STDOUT.
    >>
    >> Repeated substrings may not overlap. If more than one substring is
    >> repeated
    >> with the same length, you may print any of them. If there is no
    >> repeated
    >> substring, the result is an empty string (print nothing).
    >>
    >> Example:
    >>
    >> $ echo banana | ruby longest_repeated_substring.rb
    >> an
    >>
    >> OR
    >>
    >> $ echo banana | ruby longest_repeated_substring.rb
    >> na
    >>
    >> Make sure your code runs efficiently when passed a large text.
    >>

    >
    > Should white space and punctuation be treated as part of the
    > substring, or are they to be ignored?


    I vote that we treat all characters equally.

    James Edward Gray II
     
    James Gray, Jan 18, 2008
    #4
  5. Ruby Quiz

    Dave Thomas Guest

    On Jan 18, 2008, at 7:23 AM, Ruby Quiz wrote:

    > Repeated substrings may not overlap. If more than one substring is
    > repeated
    > with the same length, you may print any of them. If there is no
    > repeated
    > substring, the result is an empty string (print nothing).



    Must they be adjacent, or does "aaabaaa" contain the repeating
    substring "aaa"?


    Dave
     
    Dave Thomas, Jan 18, 2008
    #5
  6. Ruby Quiz

    James Gray Guest

    On Jan 18, 2008, at 10:37 AM, Dave Thomas wrote:

    > On Jan 18, 2008, at 7:23 AM, Ruby Quiz wrote:
    >
    >> Repeated substrings may not overlap. If more than one substring is
    >> repeated
    >> with the same length, you may print any of them. If there is no
    >> repeated
    >> substring, the result is an empty string (print nothing).

    >
    > Must they be adjacent, or does "aaabaaa" contain the repeating
    > substring "aaa"?


    They do not have to be adjacent. aaa would be a valid answer for
    aaabaaa.

    James Edward Gray II
     
    James Gray, Jan 18, 2008
    #6
  7. Ruby Quiz

    Philip Gatt Guest

    I hope I get some time to take a shot at this one. It looks like fun.


    On Jan 18, 2008, at 8:43 AM, James Gray wrote:

    > On Jan 18, 2008, at 10:37 AM, Dave Thomas wrote:
    >
    >> On Jan 18, 2008, at 7:23 AM, Ruby Quiz wrote:
    >>
    >>> Repeated substrings may not overlap. If more than one substring
    >>> is repeated
    >>> with the same length, you may print any of them. If there is no
    >>> repeated
    >>> substring, the result is an empty string (print nothing).

    >>
    >> Must they be adjacent, or does "aaabaaa" contain the repeating
    >> substring "aaa"?

    >
    > They do not have to be adjacent. aaa would be a valid answer for
    > aaabaaa.
    >
    > James Edward Gray II
    >
    >
     
    Philip Gatt, Jan 18, 2008
    #7
  8. Ruby Quiz

    Ken Bloom Guest

    On Fri, 18 Jan 2008 08:23:40 -0500, Ruby Quiz wrote:

    > The three rules of Ruby Quiz:
    >
    > 1. Please do not post any solutions or spoiler discussion for this quiz
    > until 48 hours have passed from the time on this message.
    >
    > 2. Support Ruby Quiz by submitting ideas as often as you can:
    >
    > http://www.rubyquiz.com/
    >
    > 3. Enjoy!
    >
    > Suggestion: A [QUIZ] in the subject of emails about the problem helps
    > everyone on Ruby Talk follow the discussion. Please reply to the
    > original quiz message, if you can.
    >
    > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

    =-=-=-=-=
    >
    > This week's Ruby Quiz is to write a script that finds the longest
    > repeated substring in a given text.
    >
    > Your program will be passed some text on STDIN and is expected to print
    > the longest repeated substring within that text to STDOUT.
    >
    > Repeated substrings may not overlap. If more than one substring is
    > repeated with the same length, you may print any of them. If there is
    > no repeated substring, the result is an empty string (print nothing).
    >
    > Example:
    >
    > $ echo banana | ruby longest_repeated_substring.rb an
    >
    > OR
    >
    > $ echo banana | ruby longest_repeated_substring.rb na
    >
    > Make sure your code runs efficiently when passed a large text.


    First testcase:
    "your banana my banana" should give " banana"

    --Ken

    --
    Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
    Department of Computer Science. Illinois Institute of Technology.
    http://www.iit.edu/~kbloom1/
     
    Ken Bloom, Jan 18, 2008
    #8
  9. Ruby Quiz

    yermej Guest

    Re: Longest Repeated Substring (#153)

    On Jan 18, 2:38 pm, Ken Bloom <> wrote:
    > First testcase:
    > "your banana my banana" should give " banana"
    >
    > --Ken
    >
    > --
    > Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
    > Department of Computer Science. Illinois Institute of Technology.http://www.iit.edu/~kbloom1/


    And a second:
    "aaaaaa" should give "aaa"

    Right?
     
    yermej, Jan 18, 2008
    #9
  10. Re: Longest Repeated Substring (#153)

    T24gSmFuIDE4LCAyMDA4IDEwOjAwIFBNLCB5ZXJtZWogPHllcm1lakBnbWFpbC5jb20+IHdyb3Rl
    Ogo+IE9uIEphbiAxOCwgMjozOCBwbSwgS2VuIEJsb29tIDxrYmwuLi5AZ21haWwuY29tPiB3cm90
    ZToKCj4gQW5kIGEgc2Vjb25kOgo+ICJhYWFhYWEiIHNob3VsZCBnaXZlICJhYWEiCj4KPiBSaWdo
    dD8KCkl0IHNob3VsZCwgb3RoZXJ3aXNlICJiYW5hbmEiIHdvdWxkIGdpdmUgImFuYSIgcmF0aGVy
    IHRoYW4gImFuIi4KCk15IHF1ZXN0aW9uIGlzIChJJ20gbm90IGZhbWlsaWFyIHdpdGggUnVieVF1
    aXogdG9vIG11Y2ggOikpOiBlcGlzb2RlCmZvY3VzIG9uIGFsZ29yaXRobSAoc3BlZWQpIG9yIHNv
    dXJjZSBjb2RlIChyZWFkYWJsZSk/CgoKLS0gClJhZG9zs2F3IEJ1s2F0CgpodHRwOi8vcmFkYXJl
    ay5qb2dnZXIucGwgLSBt82ogYmxvZwo=
     
    Rados³aw Bu³at, Jan 18, 2008
    #10
  11. Re: Longest Repeated Substring (#153)

    PiBJdCBzaG91bGQsIG90aGVyd2lzZSAiYmFuYW5hIiB3b3VsZCBnaXZlICJhbmEiIHJhdGhlciB0
    aGFuICJhbiIuCgpPciBldmVuIGJldHRlciBpdCB3b3VsZCBiZSB0aGUgc2FtZSBzdHJpbmcuCgot
    LSAKUmFkb3OzYXcgQnWzYXQKCmh0dHA6Ly9yYWRhcmVrLmpvZ2dlci5wbCAtIG3zaiBibG9nCg==
     
    Rados³aw Bu³at, Jan 18, 2008
    #11
  12. Ruby Quiz

    James Gray Guest

    Re: Longest Repeated Substring (#153)

    On Jan 18, 2008, at 3:10 PM, Rados=B3aw Bu=B3at wrote:

    > On Jan 18, 2008 10:00 PM, yermej <> wrote:
    >> On Jan 18, 2:38 pm, Ken Bloom <> wrote:

    >
    >> And a second:
    >> "aaaaaa" should give "aaa"
    >>
    >> Right?

    >
    > It should, otherwise "banana" would give "ana" rather than "an".
    >
    > My question is (I'm not familiar with RubyQuiz too much :)): episode
    > focus on algorithm (speed) or source code (readable)?


    Hopefully both. :)

    James Edward Gray II=
     
    James Gray, Jan 18, 2008
    #12
  13. Ruby Quiz

    Robert Dober Guest

    Re: Longest Repeated Substring (#153)

    MjAwOC8xLzE4IFJhZG9zs2F3IEJ1s2F0IDxyYWRlay5idWxhdEBnbWFpbC5jb20+Ogo+IE9uIEph
    biAxOCwgMjAwOCAxMDowMCBQTSwgeWVybWVqIDx5ZXJtZWpAZ21haWwuY29tPiB3cm90ZToKPiA+
    IE9uIEphbiAxOCwgMjozOCBwbSwgS2VuIEJsb29tIDxrYmwuLi5AZ21haWwuY29tPiB3cm90ZToK
    Pgo+ID4gQW5kIGEgc2Vjb25kOgo+ID4gImFhYWFhYSIgc2hvdWxkIGdpdmUgImFhYSIKPiA+Cj4g
    PiBSaWdodD8KPgo+IEl0IHNob3VsZCwgb3RoZXJ3aXNlICJiYW5hbmEiIHdvdWxkIGdpdmUgImFu
    YSIgcmF0aGVyIHRoYW4gImFuIi4KPgo+IE15IHF1ZXN0aW9uIGlzIChJJ20gbm90IGZhbWlsaWFy
    IHdpdGggUnVieVF1aXogdG9vIG11Y2ggOikpOiBlcGlzb2RlCj4gZm9jdXMgb24gYWxnb3JpdGht
    IChzcGVlZCkgb3Igc291cmNlIGNvZGUgKHJlYWRhYmxlKT8KTm9ybWFsbHkgdGhpcyBpcyBub3Qg
    dmVyeSBpbXBvcnRhbnQgYWxsIGFzcGVjdHMgY2FuIGJlIG9mIGludGVyZXN0IGJ1dApwbGVhc2Ug
    YmUgYXdhcmUgdGhhdCB0aGlzIHRpbWUgSmFtZXMgaGFzIGV4cGxpY2l0bHkgYXNrZWQgZm9yCnNv
    bHV0aW9ucyB0aGF0IGFyZSByZWFzb25hYmxlIGZhc3QgZm9yIGxvbmdlciBpbnB1dC4KR3JlYXQg
    dG8gaGF2ZSB5b3Ugam9pbiBpbiBCVFcuIFRoZSBtb3N0IGltcG9ydGFudCB0aGluZyBpcyB0bwpw
    YXJ0aWNpcGF0ZSBvZiBjb3Vyc2UuLi4KCkNoZWVycwpSb2JlcnQKLS0gCmh0dHA6Ly9ydWJ5LXNt
    YWxsdGFsay5ibG9nc3BvdC5jb20vCgotLS0KV2hlcmVvZiBvbmUgY2Fubm90IHNwZWFrLCB0aGVy
    ZW9mIG9uZSBtdXN0IGJlIHNpbGVudC4KTHVkd2lnIFdpdHRnZW5zdGVpbgo=
     
    Robert Dober, Jan 18, 2008
    #13
  14. Re: Longest Repeated Substring (#153)

    PiA+IE15IHF1ZXN0aW9uIGlzIChJJ20gbm90IGZhbWlsaWFyIHdpdGggUnVieVF1aXogdG9vIG11
    Y2ggOikpOiBlcGlzb2RlCj4gPiBmb2N1cyBvbiBhbGdvcml0aG0gKHNwZWVkKSBvciBzb3VyY2Ug
    Y29kZSAocmVhZGFibGUpPwo+Cj4gSG9wZWZ1bGx5IGJvdGguICA6KQoKSG93IGxvbmcgaW5wdXQg
    c3RyaW5nIEkgY291bGQgZXhwZWN0PwoKLS0gClJhZG9zs2F3IEJ1s2F0CgpodHRwOi8vcmFkYXJl
    ay5qb2dnZXIucGwgLSBt82ogYmxvZwo=
     
    Rados³aw Bu³at, Jan 18, 2008
    #14
  15. Ruby Quiz

    tho_mica_l Guest

    Re: Longest Repeated Substring (#153)

    > First testcase:
    > "your banana my banana" should give " banana"


    For the GNU GENERAL PUBLIC LICENSE Version 2, June 1991, I get:

    "customarily used for software interchange; or, "... some more
    whitespace

    For the GPL3 I get:

    ") Convey the object code in, or embodied in, a physical product
    (including a physical distribution medium), accompanied by "...

    If somebody can verify this.

    I think this really starts to make fun when running the script over
    Mark Twains entire work (from Gutenberg) or something similar.
     
    tho_mica_l, Jan 18, 2008
    #15
  16. Ruby Quiz

    yermej Guest

    Re: Longest Repeated Substring (#153)

    On Jan 18, 3:54 pm, tho_mica_l <> wrote:
    > > First testcase:
    > > "your banana my banana" should give " banana"

    >
    > For the GNU GENERAL PUBLIC LICENSE Version 2, June 1991, I get:
    >
    > "customarily used for software interchange; or, "... some more
    > whitespace
    >
    > For the GPL3 I get:
    >
    > ") Convey the object code in, or embodied in, a physical product
    > (including a physical distribution medium), accompanied by "...
    >
    > If somebody can verify this.
    >
    > I think this really starts to make fun when running the script over
    > Mark Twains entire work (from Gutenberg) or something similar.


    I agree on GPL3.

    How much whitespace followed your GPL2 result? I ended up with
    " 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n"
    which is 57 characters. Maybe just a difference in the text files we
    used? I used 'ruby-1.8.6/GPL'.
     
    yermej, Jan 18, 2008
    #16
  17. Ruby Quiz

    tho_mica_l Guest

    Re: Longest Repeated Substring (#153)

    > " 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n"

    It seems there is another version of this document around (at least on
    my harddisk) in which the line in the header reads " 59 Temple Place,
    Suite 330, Boston, MA 02111 USA\n" instead.

    Thanks for verifying.

    Thomas.
     
    tho_mica_l, Jan 18, 2008
    #17
  18. Ruby Quiz

    ara.t.howard Guest

    Re: Longest Repeated Substring (#153)

    On Jan 18, 2008, at 2:00 PM, yermej wrote:

    > On Jan 18, 2:38 pm, Ken Bloom <> wrote:
    >> First testcase:
    >> "your banana my banana" should give " banana"
    >>
    >> --Ken
    >>
    >> --
    >> Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
    >> Department of Computer Science. Illinois Institute of
    >> Technology.http://www.iit.edu/~kbloom1/

    >
    > And a second:
    > "aaaaaa" should give "aaa"
    >
    > Right?


    i would think that

    'aaaaaa'.longest_repeating_substring #=> 'aaaaa'

    the quiz did not say that the two strings could not overlap.

    is this correct james?

    a @ http://codeforpeople.com/
    --
    share your knowledge. it's a way to achieve immortality.
    h.h. the 14th dalai lama
     
    ara.t.howard, Jan 18, 2008
    #18
  19. Ruby Quiz

    James Gray Guest

    Re: Longest Repeated Substring (#153)

    On Jan 18, 2008, at 3:42 PM, Rados=B3aw Bu=B3at wrote:

    >>> My question is (I'm not familiar with RubyQuiz too much :)): episode
    >>> focus on algorithm (speed) or source code (readable)?

    >>
    >> Hopefully both. :)

    >
    > How long input string I could expect?


    Anybody found a good long text to work with yet? The text of the U.S. =20=

    Constitution perhaps? Tristram Shandy?

    I would say that you should handle the biggest text you possibly =20
    can. :)

    James Edward Gray II=
     
    James Gray, Jan 18, 2008
    #19
  20. Re: Longest Repeated Substring (#153)

    On 18 Jan 2008, at 23:05, ara.t.howard wrote:

    >> And a second:
    >> "aaaaaa" should give "aaa"
    >>
    >> Right?

    >
    > i would think that
    >
    > 'aaaaaa'.longest_repeating_substring #=> 'aaaaa'
    >
    > the quiz did not say that the two strings could not overlap.
    >
    > is this correct james?


    Actually the spec says "Repeated substrings may not overlap." so the
    correct answer for "aaaaaa" should be "aaa".

    /dh
     
    Denis Hennessy, Jan 19, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    366
  2. Joerg Schuster

    leftmost longest match (of disjunctions)

    Joerg Schuster, Dec 1, 2003, in forum: Python
    Replies:
    12
    Views:
    706
    Joerg Schuster
    Dec 3, 2003
  3. Ruby Quiz
    Replies:
    0
    Views:
    177
    Ruby Quiz
    Jan 24, 2008
  4. Replies:
    3
    Views:
    205
    Sherm Pendley
    Aug 3, 2005
  5. Henry Townsend

    longest common substring

    Henry Townsend, Nov 1, 2006, in forum: Perl Misc
    Replies:
    4
    Views:
    202
    Peter Scott
    Nov 2, 2006
Loading...

Share This Page