有没有一种高效的方法来测试一个字符串是否包含非重叠的子字符串以匹配正则表达式数组？

Question

有没有一种高效的方法来测试一个字符串是否包含非重叠的子字符串以匹配正则表达式数组？

3

我想测试一个字符串是否包含非重叠的子字符串以匹配以下方式的正则表达式数组：如果一个子字符串与数组中的某个项匹配，则从数组中删除相应的正则表达式并继续。我需要一个函数func(arg1, arg2)，它将接受两个参数：第一个是字符串本身，第二个是要测试的正则表达式数组。
我已阅读了一些解释（例如Regular Expressions: Is there an AND operator?），但它们没有回答这个具体问题。例如，在Javascript中，以下三个代码片段将返回true：

/(?=ab)(?=abc)(?=abcd)/gi.test("eabzzzabcde");
/(?=.*ab)(?=.*abc)(?=.*abcd)/gi.test("eabzzzabcde");
/(?=.*?ab)(?=.*?abc)(?=.*?abcd)/gi.test("eabzzzabcde");

显然，这不是我想要的结果（因为在字符串"eabzzzabcde"中，"abc"和"abcd"只是混在一起重叠了）。所以，func("eabzzzabcde", [/ab/gi, /abc/gi, /abcd/gi])应该返回false。

但是，func("Fhh, fabcw wxabcdy yz... zab.", [/ab/gi, /abc/gi, /abcd/gi])应该返回true，因为"ab"、"abc"和"abcd"子字符串没有重叠。逻辑如下：我们有一个正则表达式数组：[/ab/gi, /abc/gi, /abcd/gi]，以及原始字符串的三个（其中3等于该数组的长度）可能的非重叠、独立子字符串：fabcw、xabcdy和zab. fabcw是否与/abc/gi匹配？是的。好的，我们从数组中删除/abc/gi，对于xabcdy和zab.，我们得到[/ab/gi, /abcd/gi]。 xabcdy是否与/abcd/gi匹配？是的。好的，我们从当前数组中删除/abcd/gi，对于zab.，我们得到[/ab/gi]。 zab.是否与/ab/gi匹配？是的。在当前数组中没有更多的正则表达式了，并且我们始终回答“是”，所以返回true。 这里的棘手之处在于找到一种有效（性能不太糟糕）的方法来获取至少一个可能的“好”的非重叠子字符串组合。

更加复杂的情况是例如func("acdxbaab ababaacb", [/.*?a.*?b.*?c/gi, /.*?c.*?b.*?a/gi])。根据上面描述的逻辑，我们可以看出，如果我们取原始字符串的两个不重叠部分"acdxba"（或"cdxba"）和"abaac"（或"abaacb"、"babaac"等），第一个匹配/.*?c.*?b.*?a/gi，而第二个匹配/.*?a.*?b.*?c/gi。所以，func("acdxbaab ababaacb", [/.*?a.*?b.*?c/gi, /.*?c.*?b.*?a/gi])应该返回true。

有没有更有效的方法来解决这样的问题？

- lyrically wicked

好的，.test() 只会给你一个是否匹配的是/否答案，但如果你使用 .exec()（或 .match()），你将得到匹配的详细信息以及它在字符串中的索引，因此你应该能够利用这些信息来检查重叠。关于你的例子 "Fhh, fabcw wxabcdy yz... zab."，这些子字符串确实彼此重叠，因为 /ab/gi 将在该输入字符串中匹配三次。 - nnnnnn

一种可能性（可能不是最好的，而且可能有点混乱）：对于每个正则表达式，制作一个匹配子字符串的索引和长度列表，然后比较所有正则表达式的列表以找到非重叠的匹配项。 - Frxstrem

你的测试用例：func("Fhh，fabcw wxabcdy yz... zab。"，[/ab/gi, /abc/gi, /abcd/gi])。我认为这应该返回 false 而不是 true（因为在“wxabcdy”中全部重叠）。 - Makyen

@Makyen：“使用这三个RegExp，不可能没有重叠。” —— 我已经提到我不关心正则表达式是否重叠。我在问题中添加了透彻的逻辑澄清。 - lyrically wicked

糟糕，还差一点。没有处理好边界情况，即（1）存在多个更长目标字符串的选择，（2）第一个匹配不理想，因为在后续匹配中，较短的目标字符串部分匹配该目标字符串以及前面或后面的字母。因此，步骤＃2“查找第一个匹配项”实际上需要扩展为完整的广度优先搜索，按顺序测试每个可能的位置。 - Stephen Chung

显示剩余12条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user663031 · Accepted Answer

假设每个模式只匹配一次，那么我们可以构建一个包含它们所有排列的正则表达式：

const patterns= ['ab', 'abc', 'abcd'];
const input = "Fhh, fabcw wxabcdy yz... zab.";

// Create a regexp of the form
// (.*?ab.*?abc.*?abcd.*?)
function build(patterns) {
  return `(${['', ...patterns, ''].join('.*?')})`;
}

function match(input, patterns) {
  const regexps = [...permute(patterns)].map(build);

  // Create a regexp of the form
  // /(.*?ab.*?abc.*?abcd.*?)|(.*?ab.*?abcd.*?abc.*?)|.../
  const regexp = new RegExp(regexps.join('|'));

  return regexp.test(input);
}

// Simple permutation generator.
function *permute(a, n = a.length) {
  if (n <= 1) yield a.slice();
  else for (let i = 0; i < n; i++) {
    yield *permute(a, n - 1);
    const j = n % 2 ? 0 : i;
    [a[n-1], a[j]] = [a[j], a[n-1]];
  }
}

console.log(match(input, patterns));

如果有超过半打的模式，那么这将导致一个非常长的正则表达式。为了解决这个问题，我们可以逐个测试每个排列：

function match(input, patterns) {
  return Array.from(permute(patterns))
    .some(perm => input.match(build(perm)));
}

如果有十个模式，我们最终将进行数百万次测试。

免责声明

此处使用了ES6功能。如果需要，请回退到等效的ES5语法。
这里的输入模式是字符串。要处理正则表达式，则需要一些逻辑来从正则表达式中提取模式，并转义其中出现的任何特殊正则表达式字符。

是否有一种高效的方法来测试字符串是否包含非重叠的子字符串以匹配正则表达式数组？

我怀疑您不会称上述解决方案为“高效”，但我不知道是否有更高效的解决方案。据我所见，解决此问题的任何方法都将涉及回溯。您可以匹配前九个模式，然后发现最后一个无法匹配，因为前面九个中的一个贪婪地吃掉了第十个所需的部分，即使它本身在字符串的某个后面位置也可以被匹配。因此，我会说这个问题本质上是阶乘级别的O(n!)。