1

例如，如果它包含一定数量的某个字符，我想匹配一个子字符串。但是，我不知道该字符的确切数量，但我知道它不是负数。我将如何编写这个正则表达式？

from sys import stdin
import re
k = int(raw_input())
combo = re.compile(r'(?=(.*1.*){k})')
print [ s for s in combo.findall(stdin.readline().strip()) ]

这可能吗？如果是这样，我该怎么做？

编辑：示例输入：k = 2 字符串 = 01010

预期输出：“101”、“0101”、“1010”、“01010”

所以在每个子字符串中，它正好包含 2 个字符 '1'

4

2 回答 2

6

正则表达式是字符串，因此请随意使用您最喜欢的字符串格式化构造：

combo = re.compile(r'(?=(.*1.*){%d})' % k)

至于您编辑的问题，我找不到使用正则表达式的简单方法，以下如何？

def all_substrings(s):
    m = len(s)
    for i in range(m):
        for j in range(i, m):
            yield s[i:j+1]

s = '01010'
print [x for x in all_substrings(s) if x.count('1') == 2]
于 2013-06-10T07:57:23.690 回答
0

所以经过这么多年，有人赞成这个问题。

起初，我不记得当我在 SO 上发布问题时第一次看到这个问题的地方。不，这不是该评论所暗示的作业，而是在Google中输入了一些关键字，我在以下位置找到了问题描述：

我对 codeforces 的看法是正确的。我看到我实际上已经想出了一个解决方案并提交了它。这是我最快的解决方案：https ://codeforces.com/contest/165/submission/4171748 ：

k = int(raw_input())
 
def stable_search( zero, bin_num ):
    import collections
    c_one = ans = temp_ans = temp_z = 0
    c_zero = collections.deque()
    for f in bin_num[zero:]:
        if f == '1':
            c_zero.append(zero); zero = 0
            c_one = -~c_one
            if c_one >= k:
                ans = ans + ( temp_z * temp_ans ) + temp_z
                temp_ans = 0; temp_z = -~c_zero.popleft()
        else: temp_ans, zero = -~temp_ans, -~zero
    return ans + ( temp_z * temp_ans ) + temp_z
 
def mid(bin_num):
    return stable_search(bin_num.find('1'), bin_num)
 
def find_zeros(bin_num):
    import re
    return sum((len(sed)*-~len(sed))>>1 for sed in re.findall( '0+', bin_num))
 
if k == 0: print find_zeros(raw_input())
else: print mid(raw_input())

哎呀！看看所有的位操作（我最近一定了解了位操作）。顺便-~n说一句，只需在n.

再次查看代码，我看到正则表达式用于解决问题的一个方面（何时k为 0），但其余部分是使用我现在不确定我是否完全理解的技术完成的。这看起来像一个 2 指针问题，但我认为可能还有更多问题，特别是考虑到时间限制。

如您所见，该解决方案O(N)及时运行并且是用 python 2 编写的（当时有传言说 python 3 比 python 2 慢，所以每个人都虔诚地坚持使用 python 2，包括你的）。让我们看看用 python 3 重写它是否真的让它变慢了：

https://codeforces.com/contest/165/submission/115388714

没有！它变得更快了。

#!/usr/bin/python3
import collections
import re

def find_bin_ksubs (k: int, bin_num: str) -> int:
    tmp_z = tmp_count = count = count_1 = 0
    zeros = collections.deque()
    count_0 = bin_num.find('1')
    if count_0 == -1:
        return 0

    for b in bin_num[count_0:]:
        if b == '1':
            zeros.append(count_0)
            count_0 = 0
            count_1 += 1
            if count_1 >= k:
                count = count + (tmp_z * tmp_count) + tmp_z
                tmp_count = 0
                tmp_z = zeros.popleft() + 1
        else:
            count_0 += 1
            tmp_count += 1

    return count + (tmp_z * tmp_count) + tmp_z


def find_empties (bin_num: str) -> int:
    reg = re.compile(r'0+')
    return sum((count ** 2 + count) >> 1 \
        for zeros in reg.findall(bin_num) if (count := len(zeros)))


if __name__ == '__main__':
    if (k := int (input ())) == 0:
        print (find_empties(input()))
    else:
        print (find_bin_ksubs(k, input()))

编辑

公平地说，计算机自 2013 年以来一直在发展，所以我决定再上传一次 python2 解决方案，只是为了公平比较……好吧，看来谣言仍然是真的：

https://codeforces.com/contest/165/submission/115434939

于 2021-05-06T06:59:33.047 回答