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

Question

我正在处理《哥德尔、艾舍尔、巴赫》第2章中的MIU系统问题。

其中一条规则如下：

规则III：如果你的集合中有一个字符串包含III，则可以新建一个字符串，将III替换为U。

这意味着字符串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(.*)/有所帮助，但似乎无法生成每个可能的匹配项，只能找到第一个。

是否有一种方法可以生成每个可能的匹配项？

（注意，我可以想到完全手动处理的方法，但希望使用内置工具、正则表达式或其他方式找到更好的方法。）

（编辑后以澄清重叠需要。）

- Colin Dabritz

---

你是在询问如何获取字符串中所有出现的 III，包括重叠匹配，并将它们返回到一个数组中吗？ - Ray Toal

是的，根据示例来看。例如，MIIII应该有两个匹配项，分别为M[III]I和MI[III]。（它们会变成MUI和MIU）。Exec看起来很有前途，但它无法处理重叠的情况。 - Colin Dabritz

RegExp.exec 可以为您工作，但您需要使用匹配对象，就像 Kolink 的答案中所示。在这种情况下，indexOf 可能更好，但正则表达式肯定更通用。 - Ray Toal

Hofstadter 也在俄勒冈州待过一段时间，是吗？ - Andrew Cheong

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演示上面的代码。

- Niet the Dark Absol

---

嗯，为什么是加1而不是减1？这似乎并没有解决我的问题，我还在试探。我会找到答案后再回报。 - Colin Dabritz

我不确定为什么你认为-1会起作用。你需要向前移动字符串，而不是向后。向后移动会重复找到完全相同的匹配项，并给你一个无限循环。在答案中编辑了一个JSFiddle链接。 - Niet the Dark Absol

误读了上面的内容，我直接编辑了最后一个索引，结果发现这样做没什么用。这个方法看起来有效，非常感谢！ - Colin Dabritz

不错，我在谷歌上搜索了一下如何在 JavaScript 中进行正则表达式搜索，考虑到重叠匹配。大概找了30分钟，直到我找到这篇帖子，其中提供了简单的 regex.lastIndex = match.index + 1 解决方案。谢谢！ - BobuSumisu

Answer 2

有时候正则表达式会过于复杂，针对你的情况，使用简单的indexOf也许更为适合！

下面这个方法，虽然有些取巧，但你可以将其改造成漂亮、可重用的代码：

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

它可以很好地处理重叠的部分，并且对我来说，indexOf 看起来更加简单。

- Ray Toal

---

是的，这个案例非常简单。它们会变得更加复杂，理想情况下应该是基本上没有限制的。 - Colin Dabritz

同意。对于 Mx → Mxx 规则，您需要更强大的东西 :) - Ray Toal

是的，幸运的是正则表达式可以很好地处理Mx -> Mxx的情况：newTheorems.push( startingTheorem.replace( /(M)(.+)/i, "$1$2$2" ) ); - Colin Dabritz

其实，这比那还要简单：function Rule2(s) {return s + s.substring(1);}因为在MIU谜题中，所有字符串都以“M”开头！ - Ray Toal

真的，很好地利用了内置工具。虽然这让我学习 JavaScript 正则表达式变得更容易了，但我已经知道 C 了 ;) - Colin Dabritz