How to get all possible overlapping matches for a string

I'm working on the MIU system problem from "Gödel, Escher, Bach" chapter 2.

One of the rules states

Rule III: If III occurs in one of the strings in your collection, you may make a new string with U in place of III.

Which means that the string MIII can become MU, but for other, longer strings there may be multiple possibilities [matches in brackets]:

  • MIIII could yield
    • M[III]I >> MUI
    • MI[III] >> MIU
  • MUIIIUIIIU could yield
  • MUIIIIU could yield
    • MU[III]IU >> MUUIU
    • MUI[III]U >> MUIUU

Clearly regular expressions such as /(.*)III(.*)/ are helpful, but I can't seem to get them to generate every possible match, just the first one it happens to find.

Is there a way to generate every possible match?

(Note, I can think of ways to do this entirely manually, but I am hoping there is a better way using the built in tools, regex or otherwise)

(Edited to clarify overlapping needs.)



Here's the regex you need: /III/g - simple enough, right? Now here's how you use it:

var text = "MUIIIUIIIU", find = "III", replace "U",
    regex = new RegExp(find,"g"), matches = [], match;
while(match = regex.exec(text)) {
    regex.lastIndex = match.index+1;

That regex.lastIndex... line overrides the usual regex behaviour of not matching results that overap. Also I'm using a RegExp constructor to make this more flexible. You could even build it into a function this way.

Now you have an array of match objects, you can do this:

matches.forEach(function(m) { // older browsers need a shim or old-fashioned for loop

EDIT: Here is a JSFiddle demonstrating the above code.


Sometimes regexes are overkill. In your case a simple indexOf might be fine too!

Here is, admittedly, a hack, but you can transform it into pretty, reusable code on your own:

var results = [];
for (var i = 0; true; i += 1) {
    i = s.indexOf("III", i);
    if (i === -1) {
console.log("Match positions: " + JSON.stringify(results));

It takes care of overlaps just fine, and at least to me, the indexOf just looks simpler.


Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.