如何获得字符串的所有可能的重叠匹配

Question

我正在研究"Gödel,Escher,Bach"第2章中的MIU系统问题.

其中一条规则称

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.

这意味着字符串MIII可以变为MU,但对于其他更长的字符串,可能存在多种可能性[括号中的匹配]:

• MIIII 可以屈服
  • M[III]I >> MUI
  • MI[III] >> MIU
• MUIIIUIIIU 可以屈服
  • MU[III]UIIIU >> MUUUIIIU
  • MUIIIU[III]U >> MUIIIUUU
• MUIIIIU 可以屈服
  • MU[III]IU >> MUUIU
  • MUI[III]U >> MUIUU

显然正则表达式是/(.*)III(.*)/有帮助的,但我似乎无法让它们生成所有可能的匹配,只是它碰巧找到的第一个.

有没有办法产生每一个可能的匹配？

(注意,我可以想办法完全手动完成这个,但我希望有更好的方法使用内置工具,正则表达式或其他方式)

(编辑以澄清重叠的需求.)

Answer 1

这是你需要的正则表达式:/III/g- 够简单吧？现在这是你如何使用它:

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

该regex.lastIndex...行覆盖了通常的正则表达式行为,即不匹配过度结果.此外,我正在使用RegExp构造函数来使其更灵活.你甚至可以用这种方式将它构建成一个函数.

现在你有一个匹配对象数组,你可以这样做:

matches.forEach(function(m) { // older browsers need a shim or old-fashioned for loop
    console.log(text.substr(0,m.index)+replace+text.substr(m.index+find.length));
});

编辑: 这是一个JSFiddle演示上面的代码.