CODEWITHSUNDEEP
rubystringpattern-matching
user2398029
user2398029

Reputation: 6937

Find longest repeated substring with matched parentheses in ruby

Consider a set of strings as follows:

aa(bb(c)dd)
aeeff(bb(cd)eee)
(bb(c)dd)(bb(cd(eee

Even though the longest repeated non-overlapping substring is (bb(cd)eee (10 chars), the longest repeated substring with matched parentheses is (bb(c)ee) (9 chars).

I can easily find the longest non-overlapping repeated substring, but how can this be extended to matching parentheses?

Upvotes: 0

Views: 405

Answers (1)

Cary Swoveland
Cary Swoveland

Reputation: 110675

As I understand you want the longest string within a single line that begins with "(" and ends with ")" and contains "balanced parentheses". In addition, the substring is to be a "repeated" substring, but that has not been defined, so I've disregarded that requirement.

balanced_parens? (below) is from my answer here. 

def longest_balanced(str)
  str.lines.map { |s| longest_by_line(s.chomp) }.max_by(&:size)
end 

def longest_by_line(str)
  str.size.downto(1).find do |n|
    str.each_char.each_cons(n) do |a|
      s = a.join
      return s if (s =~ /\A\(.*\)\z/)  && balanced_parens?(s)
    end
  end
  nil
end

def balanced_parens?(str)
  pstr = str.gsub(/[^()]/,"")
  while pstr.gsub!("()", "")
  end
  pstr.empty?
end

str =<<_
aa(bb(c)dd)
aeeff(bb(cd)eee)
(bb(c)dd)(bb(cd(eee
_

longest_balanced str
  #=> "(bb(cd)eee)"

Upvotes: 2

Related Questions