Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Ruby (http://www.velocityreviews.com/forums/f66-ruby.html)
-   -   [QUIZ] Longest Repeated Substring (#153) (http://www.velocityreviews.com/forums/t847506-quiz-longest-repeated-substring-153-a.html)

Ruby Quiz 01-18-2008 01:23 PM

[QUIZ] Longest Repeated Substring (#153)
 
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 01-18-2008 02:30 PM

Re: [QUIZ] Longest Repeated Substring (#153)
 
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 01-18-2008 03:49 PM

Re: [QUIZ] Longest Repeated Substring (#153)
 
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 01-18-2008 03:53 PM

Re: [QUIZ] Longest Repeated Substring (#153)
 
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 01-18-2008 04:37 PM

Re: [QUIZ] Longest Repeated Substring (#153)
 

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 01-18-2008 04:43 PM

Re: [QUIZ] Longest Repeated Substring (#153)
 
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 01-18-2008 04:50 PM

Re: [QUIZ] Longest Repeated Substring (#153)
 
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 01-18-2008 08:38 PM

Re: [QUIZ] Longest Repeated Substring (#153)
 
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/

yermej 01-18-2008 08:59 PM

Re: Longest Repeated Substring (#153)
 
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/~kbloom1/


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

Right?

Radosław Bułat 01-18-2008 09:10 PM

Re: Longest Repeated Substring (#153)
 
T24gSmFuIDE4LCAyMDA4IDEwOjAwIFBNLCB5ZXJtZWogPHllcm 1lakBnbWFpbC5jb20+IHdyb3Rl
Ogo+IE9uIEphbiAxOCwgMjozOCBwbSwgS2VuIEJsb29tIDxrYm wuLi5AZ21haWwuY29tPiB3cm90
ZToKCj4gQW5kIGEgc2Vjb25kOgo+ICJhYWFhYWEiIHNob3VsZC BnaXZlICJhYWEiCj4KPiBSaWdo
dD8KCkl0IHNob3VsZCwgb3RoZXJ3aXNlICJiYW5hbmEiIHdvdW xkIGdpdmUgImFuYSIgcmF0aGVy
IHRoYW4gImFuIi4KCk15IHF1ZXN0aW9uIGlzIChJJ20gbm90IG ZhbWlsaWFyIHdpdGggUnVieVF1
aXogdG9vIG11Y2ggOikpOiBlcGlzb2RlCmZvY3VzIG9uIGFsZ2 9yaXRobSAoc3BlZWQpIG9yIHNv
dXJjZSBjb2RlIChyZWFkYWJsZSk/CgoKLS0gClJhZG9zs2F3IEJ1s2F0CgpodHRwOi8vcmFkYXJl
ay5qb2dnZXIucGwgLSBt82ogYmxvZwo=



All times are GMT. The time now is 08:22 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.