如何获得字符串的所有可能的重叠匹配 [英] How to get all possible overlapping matches for a string

问题描述

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

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

其中一条规则是

规则III：如果III出现在你的集合中的一个字符串中，你可以用U代替III创建一个新的字符串。

这意味着字符串 MIII 可以成为 MU ，但对于其他更长的字符串，可能有多种可能性[括号中的匹配]：

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

• MIIII 可以产生
  
  
  
  • M [III]我 >> MUI
  
  
  • MI [III] >> MIU
  
  
  • MIIII could yield
    • M[III]I >> MUI
    • MI[III] >> MIU
    
    
    • MU [III] UIIIU >> MUUUIIIU
    
    
    • MUIIIU [III] U >> MUIIIUUU
    
    
    • MU[III]UIIIU >> MUUUIIIU
    • MUIIIU[III]U >> MUIIIUUU
    
    
    • MU [III] IU >> MUUIU
    
    
    • MUI [III] U >> MUIUU
    
    
    • MU[III]IU >> MUUIU
    • MUI[III]U >> MUIUU

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

    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.)

    推荐答案

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

    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)) {
        matches.push(match);
        regex.lastIndex = match.index+1;
    }
    

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

    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
        console.log(text.substr(0,m.index)+replace+text.substr(m.index+find.length));
    });
    

    编辑： 这里是一个JSFiddle，演示了上面的代码。

    Here is a JSFiddle demonstrating the above code.

    这篇关于如何获得字符串的所有可能的重叠匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！