[QUIZ] Longest Repeated Substring (#153)

[Ruby Quiz]

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.

 

[James Gray]

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

 

[Denis Hennessy]

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

 

[James Gray]

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

 

[Dave Thomas]

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

 

[James Gray]

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]

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

 

[Ken Bloom]

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

 

[yermej]

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

--Ken

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

Right?

 

[Rados³aw Bu³at]

T24gSmFuIDE4LCAyMDA4IDEwOjAwIFBNLCB5ZXJtZWogPHllcm1lakBnbWFpbC5jb20+IHdyb3Rl
Ogo+IE9uIEphbiAxOCwgMjozOCBwbSwgS2VuIEJsb29tIDxrYmwuLi5AZ21haWwuY29tPiB3cm90
ZToKCj4gQW5kIGEgc2Vjb25kOgo+ICJhYWFhYWEiIHNob3VsZCBnaXZlICJhYWEiCj4KPiBSaWdo
dD8KCkl0IHNob3VsZCwgb3RoZXJ3aXNlICJiYW5hbmEiIHdvdWxkIGdpdmUgImFuYSIgcmF0aGVy
IHRoYW4gImFuIi4KCk15IHF1ZXN0aW9uIGlzIChJJ20gbm90IGZhbWlsaWFyIHdpdGggUnVieVF1
aXogdG9vIG11Y2ggOikpOiBlcGlzb2RlCmZvY3VzIG9uIGFsZ29yaXRobSAoc3BlZWQpIG9yIHNv
dXJjZSBjb2RlIChyZWFkYWJsZSk/CgoKLS0gClJhZG9zs2F3IEJ1s2F0CgpodHRwOi8vcmFkYXJl
ay5qb2dnZXIucGwgLSBt82ogYmxvZwo=

 

[Rados³aw Bu³at]

PiBJdCBzaG91bGQsIG90aGVyd2lzZSAiYmFuYW5hIiB3b3VsZCBnaXZlICJhbmEiIHJhdGhlciB0
aGFuICJhbiIuCgpPciBldmVuIGJldHRlciBpdCB3b3VsZCBiZSB0aGUgc2FtZSBzdHJpbmcuCgot
LSAKUmFkb3OzYXcgQnWzYXQKCmh0dHA6Ly9yYWRhcmVrLmpvZ2dlci5wbCAtIG3zaiBibG9nCg==

 

[James Gray]

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=

 

[Robert Dober]

MjAwOC8xLzE4IFJhZG9zs2F3IEJ1s2F0IDxyYWRlay5idWxhdEBnbWFpbC5jb20+Ogo+IE9uIEph
biAxOCwgMjAwOCAxMDowMCBQTSwgeWVybWVqIDx5ZXJtZWpAZ21haWwuY29tPiB3cm90ZToKPiA+
IE9uIEphbiAxOCwgMjozOCBwbSwgS2VuIEJsb29tIDxrYmwuLi5AZ21haWwuY29tPiB3cm90ZToK
Pgo+ID4gQW5kIGEgc2Vjb25kOgo+ID4gImFhYWFhYSIgc2hvdWxkIGdpdmUgImFhYSIKPiA+Cj4g
PiBSaWdodD8KPgo+IEl0IHNob3VsZCwgb3RoZXJ3aXNlICJiYW5hbmEiIHdvdWxkIGdpdmUgImFu
YSIgcmF0aGVyIHRoYW4gImFuIi4KPgo+IE15IHF1ZXN0aW9uIGlzIChJJ20gbm90IGZhbWlsaWFy
IHdpdGggUnVieVF1aXogdG9vIG11Y2ggOikpOiBlcGlzb2RlCj4gZm9jdXMgb24gYWxnb3JpdGht
IChzcGVlZCkgb3Igc291cmNlIGNvZGUgKHJlYWRhYmxlKT8KTm9ybWFsbHkgdGhpcyBpcyBub3Qg
dmVyeSBpbXBvcnRhbnQgYWxsIGFzcGVjdHMgY2FuIGJlIG9mIGludGVyZXN0IGJ1dApwbGVhc2Ug
YmUgYXdhcmUgdGhhdCB0aGlzIHRpbWUgSmFtZXMgaGFzIGV4cGxpY2l0bHkgYXNrZWQgZm9yCnNv
bHV0aW9ucyB0aGF0IGFyZSByZWFzb25hYmxlIGZhc3QgZm9yIGxvbmdlciBpbnB1dC4KR3JlYXQg
dG8gaGF2ZSB5b3Ugam9pbiBpbiBCVFcuIFRoZSBtb3N0IGltcG9ydGFudCB0aGluZyBpcyB0bwpw
YXJ0aWNpcGF0ZSBvZiBjb3Vyc2UuLi4KCkNoZWVycwpSb2JlcnQKLS0gCmh0dHA6Ly9ydWJ5LXNt
YWxsdGFsay5ibG9nc3BvdC5jb20vCgotLS0KV2hlcmVvZiBvbmUgY2Fubm90IHNwZWFrLCB0aGVy
ZW9mIG9uZSBtdXN0IGJlIHNpbGVudC4KTHVkd2lnIFdpdHRnZW5zdGVpbgo=

 

[Rados³aw Bu³at]

PiA+IE15IHF1ZXN0aW9uIGlzIChJJ20gbm90IGZhbWlsaWFyIHdpdGggUnVieVF1aXogdG9vIG11
Y2ggOikpOiBlcGlzb2RlCj4gPiBmb2N1cyBvbiBhbGdvcml0aG0gKHNwZWVkKSBvciBzb3VyY2Ug
Y29kZSAocmVhZGFibGUpPwo+Cj4gSG9wZWZ1bGx5IGJvdGguICA6KQoKSG93IGxvbmcgaW5wdXQg
c3RyaW5nIEkgY291bGQgZXhwZWN0PwoKLS0gClJhZG9zs2F3IEJ1s2F0CgpodHRwOi8vcmFkYXJl
ay5qb2dnZXIucGwgLSBt82ogYmxvZwo=

 

[tho_mica_l]

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.

 

[yermej]

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

 

[tho_mica_l]

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

 

[ara.t.howard]

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/

 

[James Gray]

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=

 

[Denis Hennessy]

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