Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > [QUIZ] Longest Repeated Substring (#153)

Reply
Thread Tools

[QUIZ] Longest Repeated Substring (#153)

 
 
Ruby Quiz
Guest
Posts: n/a
 
      01-18-2008
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.

 
Reply With Quote
 
 
 
 
James Gray
Guest
Posts: n/a
 
      01-18-2008
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


 
Reply With Quote
 
 
 
 
Denis Hennessy
Guest
Posts: n/a
 
      01-18-2008
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

 
Reply With Quote
 
James Gray
Guest
Posts: n/a
 
      01-18-2008
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

 
Reply With Quote
 
Dave Thomas
Guest
Posts: n/a
 
      01-18-2008

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

 
Reply With Quote
 
James Gray
Guest
Posts: n/a
 
      01-18-2008
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


 
Reply With Quote
 
Philip Gatt
Guest
Posts: n/a
 
      01-18-2008
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
>
>



 
Reply With Quote
 
Ken Bloom
Guest
Posts: n/a
 
      01-18-2008
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/
 
Reply With Quote
 
yermej
Guest
Posts: n/a
 
      01-18-2008
On Jan 18, 2:38 pm, Ken Bloom <(E-Mail Removed)> 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?
 
Reply With Quote
 
Radosław Bułat
Guest
Posts: n/a
 
      01-18-2008
T24gSmFuIDE4LCAyMDA4IDEwOjAwIFBNLCB5ZXJtZWogPHllcm 1lakBnbWFpbC5jb20+IHdyb3Rl
Ogo+IE9uIEphbiAxOCwgMjozOCBwbSwgS2VuIEJsb29tIDxrYm wuLi5AZ21haWwuY29tPiB3cm90
ZToKCj4gQW5kIGEgc2Vjb25kOgo+ICJhYWFhYWEiIHNob3VsZC BnaXZlICJhYWEiCj4KPiBSaWdo
dD8KCkl0IHNob3VsZCwgb3RoZXJ3aXNlICJiYW5hbmEiIHdvdW xkIGdpdmUgImFuYSIgcmF0aGVy
IHRoYW4gImFuIi4KCk15IHF1ZXN0aW9uIGlzIChJJ20gbm90IG ZhbWlsaWFyIHdpdGggUnVieVF1
aXogdG9vIG11Y2ggOikpOiBlcGlzb2RlCmZvY3VzIG9uIGFsZ2 9yaXRobSAoc3BlZWQpIG9yIHNv
dXJjZSBjb2RlIChyZWFkYWJsZSk/CgoKLS0gClJhZG9zs2F3IEJ1s2F0CgpodHRwOi8vcmFkYXJl
ay5qb2dnZXIucGwgLSBt82ogYmxvZwo=

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
My Custom Longest Common Substring which searches for a pattern failson certain strings Alec Taylor C++ 1 11-14-2011 06:07 PM
Custom Longest Common Substring which includes a number fails whenword appears before number Alec Taylor C++ 1 11-14-2011 06:07 PM
[SUMMARY] Longest Repeated Substring (#153) Ruby Quiz Ruby 0 01-24-2008 04:11 PM
longest common substring Henry Townsend Perl Misc 4 11-02-2006 02:24 PM
Longest Sites Name With Worlds Longest Stuffs... Vijay Murthy Computer Information 0 02-04-2006 09:57 AM



Advertisments