python - 如何使用 RE 查找字符串中的多个平衡大小匹配项？

Question

我将一个问题转化为模式匹配问题，并尝试使用 RE 来解决它。

转换后的问题:给定一个“0/1”字符串，例如s = '111100111111100111111001'，尝试找到恰好3个子字符串匹配项:

a '1', followed by arbitrary number of any characters, and then 2 consecutive '1's, and the total size of the match is at least 4.

上述要求可以编码为 RE 模式:'1.{1,}11'。并且也接受相反的模式:'11.{1,}1'。并且，任意2个相邻匹配的间隔应消耗尽可能少的字符。

这一切都翻译为以下代码:

> import re
> s = '111100111111100111111001'
> p = '.*?(1.{1,}11|11.{1,}1).*?(1.{1,}11|11.{1,}1).*?(1.{1,}11|11.{1,}1).*?'
> ret = re.match(p, s)
> ret.groups()

结果:

> ('1111001111111', '1111', '11001')

从这个意义上说，这个结果不错，但不是最佳:每场比赛的长度应尽可能平衡。

精炼结果应为:

('1111001', '1111111', 11111001')

但是我如何使用 RE 来施加这个约束呢？

Answer 1

我只能想到这个:

var input = '111100111111100111111001';

for (var i = input.length; i >= 4; i--) {
  var matches = input.match(new RegExp('.{' + i + '}', 'g'));
  
  var output = matches.filter(x => /^1.+1$/.test(x));
  
  if (output.length === 3) {
    console.log(output)
  }
}

Starting with 1, ending with 1 and having at least 4 characters

因此，您的示例输入也应该匹配。如您所见，有很多输出可以匹配。

1111111
^^^^
1111111
 ^^^^
1111111
  ^^^^
1111111
   ^^^^
1111111
^^^^^
1111111
 ^^^^^
1111111
  ^^^^^
1111111
^^^^^^
1111111
 ^^^^^^
1111111
^^^^^^^