[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Longest Repeated Substring (#153

James Gray

1/18/2008 1:24:00 PM

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

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.
58 Answers

James Gray

1/18/2008 2:30:00 PM

0

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

Denis Hennessy

1/18/2008 3:50:00 PM

0

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

James Gray

1/18/2008 3:53:00 PM

0

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

Dave Thomas

1/18/2008 4:37:00 PM

0


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

James Gray

1/18/2008 4:43:00 PM

0

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

1/18/2008 4:50:00 PM

0

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

Ken Bloom

1/18/2008 8:38:00 PM

0

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

yermej

1/18/2008 9:00:00 PM

0

On Jan 18, 2:38 pm, Ken Bloom <kbl...@gmail.com> 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...

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

Right?

Radoslaw Bulat

1/18/2008 9:10:00 PM

0

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

Radoslaw Bulat

1/18/2008 9:15:00 PM

0

PiBJdCBzaG91bGQsIG90aGVyd2lzZSAiYmFuYW5hIiB3b3VsZCBnaXZlICJhbmEiIHJhdGhlciB0
aGFuICJhbiIuCgpPciBldmVuIGJldHRlciBpdCB3b3VsZCBiZSB0aGUgc2FtZSBzdHJpbmcuCgot
LSAKUmFkb3OzYXcgQnWzYXQKCmh0dHA6Ly9yYWRhcmVrLmpvZ2dlci5wbCAtIG3zaiBibG9nCg==