# Re: Longest Repeated Substring (#153)

**URL:** <https://www.ruby-forum.com/t/re-longest-repeated-substring-153/126756>\
**Category:** Ruby\
**Created:** [January 21, 2008, 11:38pm UTC](https://www.ruby-forum.com/t/re-longest-repeated-substring-153/126756 "2008-01-21T23:38:29Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [January 21, 2008, 11:38pm UTC](https://www.ruby-forum.com/t/re-longest-repeated-substring-153/126756/1 "2008-01-21T23:38:29Z")

</div>

My solution finds substrings of length n, groups the identical ones  
together in a hash of their starting indices, prunes out cases where two  
of the “repeated” substring overlap each other, and then looks in the  
same places for substrings of length n+1.

The aggressive pruning does, however, cause it to fail in the case where  
a substring that overlaps at one length does not overlap at a higher  
length. For example, take the string “aaaaaa”. The substring “aa” exists  
at indicies [0,1,2,3,4]. My program will prune that down to [0,2,4]. It  
will then record the substring of length 3 that starts at each of  
[0,2,4], prune out the ones that start at 2 (overlaps with the one  
startign at 0) and 4 (goes out of bounds), leaving only an unrepeated  
substring, and would thus fall back and print “aa,” even though the  
correct answer is “aaa,” because the index of 3 had already been pruned.

On the other hand, the aggressive pruning does make my program somewhat  
fast. It takes about 45s on Also Sprach Zarathustra.

text = ARGF.read

substr\_locs = {}

text.split(//).each\_with\_index do |c,idx|  
if substr\_locs[c]  
substr\_locs[c] \<\< idx  
else  
substr\_locs[c] = [idx]  
end  
end

substr\_locs.each\_pair do |substr,locs|  
substr\_locs.delete(substr) if locs.length == 1  
end

len = 1  
done = false  
until done  
len += 1  
new\_substr\_locs = {}  
substr\_locs.each\_pair do |substr,locs|  
locs.each do |idx|  
s = text[idx,len]  
next if idx+len\>text.length  
if new\_substr\_locs[s]  
new\_substr\_locs[s] \<\< idx  
else  
new\_substr\_locs[s] = [idx]  
end  
end  
end  
##Must reduce for the case where a substring overlaps itself  
new\_substr\_locs.each\_key do |s|  
locs = new\_substr\_locs[s]  
idx = 1  
while idx \< locs.length  
if locs[idx]-locs[idx-1] \< len  
locs.delete\_at(idx)  
else  
idx += 1  
end  
end  
new\_substr\_locs.delete(s) if locs.length == 1  
end  
unless new\_substr\_locs.keys.empty?  
substr\_locs = new\_substr\_locs  
else  
done = true  
end  
end  
puts substr\_locs.keys.first

```
  ____________________________________________________________________________________

```

Looking for last minute shopping deals?  
Find them fast with Yahoo! Search.  
[http://tools.search.yahoo.com/newsearch/category.php?category=shopping](http://tools.search.yahoo.com/newsearch/category.php?category=shopping)

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [January 23, 2008, 6:36pm UTC](https://www.ruby-forum.com/t/re-longest-repeated-substring-153/126756/2 "2008-01-23T18:36:23Z")

</div>

cannot use regex, i suppose:

(.{aNumber}).\*\1

where aNumber = 2…x (x=text.length/2), until regex ‘response’ is  
‘nil’

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [January 23, 2008, 7:09pm UTC](https://www.ruby-forum.com/t/re-longest-repeated-substring-153/126756/3 "2008-01-23T19:09:46Z")

</div>

On Jan 23, 2008, at 11:35 AM, Raffa wrote:

> cannot use regex, i suppose:
> 
> (.{aNumber}).\*\1
> 
> where aNumber = 2…x (x=text.length/2), until regex ‘response’ is  
> ‘nil’

You can use whatever you like.

Try it out on War & Peace though and see how it does. 🙂

James Edward G. II

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [January 23, 2008, 7:22pm UTC](https://www.ruby-forum.com/t/re-longest-repeated-substring-153/126756/4 "2008-01-23T19:22:47Z")

</div>

Why not?  
The simplest solution could be:

def longest\_repeated\_substring str  
(str.size/2).downto(1) { |i|  
/(.{#{i}}).\*\1/m =~ str and return $1  
}  
nil  
end

but it’s too slow;

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [January 24, 2008, 6:40am UTC](https://www.ruby-forum.com/t/re-longest-repeated-substring-153/126756/5 "2008-01-24T06:40:59Z")

</div>

On Wed, 23 Jan 2008 13:21:31 -0500, SERGEY VOLKOV wrote:

> but it’s too slow;
> 
> On Jan 23, 2008 12:35 PM, Raffa [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:
> 
> > cannot use regex, i suppose:
> > 
> > (.{aNumber}).\*\1
> > 
> > where aNumber = 2…x (x=text.length/2), until regex ‘response’ is ‘nil’

Well, one would think that the absolute simplest solution is  
/(._+)._\1/,  
but that’s what I was testing when I invented the “your banana my  
banana”  
test case. (Which it failed, returning only “y” as the repeated  
substring).

Yours is a nice extension of this basic idea.

–Ken

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [January 24, 2008, 1:18pm UTC](https://www.ruby-forum.com/t/re-longest-repeated-substring-153/126756/6 "2008-01-24T13:18:05Z")

</div>

It’s linear search for repeated substring length,  
I’ve tried binary search, too slow too