How to get possibly overlapping matches in a string

Question

I'm looking for a way, either in Ruby or Javascript, that will give me all matches, possibly overlapping, within a string against a regexp.

---

Let's say I have str = "abcadc", and I want to find occurrences of a followed by any number of characters, followed by c. The result I'm looking for is ["abc", "adc", "abcadc"]. Any ideas on how I can accomplish this?

str.scan(/a.*c/) will give me ["abcadc"], str.scan(/(?=(a.*c))/).flatten will give me ["abcadc", "adc"].

Answer 1

def matching_substrings(string, regex)   string.size.times.each_with_object([]) do |start_index, maching_substrings|     start_index.upto(string.size.pred) do |end_index|       substring = string[start_index..end_index]       maching_substrings.push(substring) if substring =~ /^#{regex}$/     end   end end  matching_substrings('abcadc', /a.*c/) # => ["abc", "abcadc", "adc"] matching_substrings('foobarfoo', /(\w+).*\1/)    # => ["foobarf",   #     "foobarfo",   #     "foobarfoo",   #     "oo",   #     "oobarfo",   #     "oobarfoo",   #     "obarfo",   #     "obarfoo",   #     "oo"] matching_substrings('why is this downvoted?', /why.*/)   # => ["why",   #     "why ",   #     "why i",   #     "why is",   #     "why is ",   #     "why is t",   #     "why is th",   #     "why is thi",   #     "why is this",   #     "why is this ",   #     "why is this d",   #     "why is this do",   #     "why is this dow",   #     "why is this down",   #     "why is this downv",   #     "why is this downvo",   #     "why is this downvot",   #     "why is this downvote",   #     "why is this downvoted",   #     "why is this downvoted?"] 

Answer 2

In Ruby you could achieve the expected result using:

str = "abcadc"
[/(a[^c]*c)/, /(a.*c)/].flat_map{ |pattern| str.scan(pattern) }.reduce(:+)
# => ["abc", "adc", "abcadc"]

Whether this way works for you is highly dependent on what you really want to achieve.

I tried to put this into a single expression but I couldn't make it work. I would really like to know if there is some scientific reason this cannot be parsed by regular expressions or if I just don't know enough about Ruby's parser Oniguruma to do it.

Answer 3

You want all possible matches, including overlapping ones. As you've noted, the lookahead trick from "How to find overlapping matches with a regexp?" doesn't work for your case.

The only thing I can think of that will work in the general case is to generate all of the possible substrings of the string and check each one against an anchored version of the regex. This is brute-force, but it works.

Ruby:

def all_matches(str, regex)
  (n = str.length).times.reduce([]) do |subs, i|
     subs += [*i..n].map { |j| str[i,j-i] }
  end.uniq.grep /^#{regex}$/
end

all_matches("abcadc", /a.*c/) 
#=> ["abc", "abcadc", "adc"]

Javascript:

function allMatches(str, regex) {
  var i, j, len = str.length, subs={};
  var anchored = new RegExp('^' + regex.source + '$');
  for (i=0; i<len; ++i) {
    for (j=i; j<=len; ++j) {
       subs[str.slice(i,j)] = true;
    }
  }
  return Object.keys(subs).filter(function(s) { return s.match(anchored); });
}

Answer 4

In JS:

function extract_ov_matches(r, s) {
  var res = [], cur;
  r = RegExp('^(?:' + r.source + ')$', r.toString().replace(/^[\s\S]*\/(\w*)$/, '$1').replace('g',''));
  for (var q = 0; q < s.length; ++q)
    for (var w = q; w <= s.length; ++w)
      if (r.test(cur = s.substring(q, w)))
        res.push(cur);
  return res;
}
document.body.innerHTML += "<pre>" + JSON.stringify(extract_ov_matches( /a.*c/g, 'abcadc' ), 0, 4) + "</pre>";

The point here is that you need to create all possible permutations of the input string and then return those that FULLY match the supplied pattern.

Overview of the extract_ov_matches function

• r is the supplied regex (a compiled regex object, with flags)
• s is the input string
• RegExp('^(?:' + r.source + ')$', r.toString().replace(/^[\s\S]*\/(\w*)$/, '$1').replace('g','')); recreates the regex supplied with anchors (^ for start of string and $ for end of string) to match the whole string and the g flag is removed (because the regex will be used with RegExp#test)
• for (var q = 0; q < s.length; ++q) for (var w = q; w <= s.length; ++w) are used to create all input string permutations
• if (r.test(cur = s.substring(q, w))) res.push(cur);: if the current permutation fully matches the pattern, it is added to res, that will get returned eventually.