黑客周代码33模式国家

Question

嗨，我一直在问Hackerrank这个问题。 我尝试过在python中使用regex。但它在测试用例“1001010001”中失败。 谁能帮忙吗？它的输出为2，但预期输出为3。 （如1001 101 10001）。python实际上是如何处理这个问题的（从算法的角度来看？）在

https://www.hackerrank.com/contests/w33/challenges/pattern-count

import re
text=(raw_input().strip('\n'))
patregex=re.compile(r'1(0)*1')
p=patregex.findall(text)
print(len(p))

Answer 1

正则表达式不计算重叠匹配数。在

但是，您可以轻松地修改代码，以：

import re

patregex=re.compile(r'10*1')

text= raw_input().strip('\n')

cnt = 0
pos = 0
match = patregex.search(text)
while match:
    match = patregex(text,match.end()-1)
    cnt += 1
print(cnt)

所以在这里，当我们找到一个match时，我们将尝试从另一个匹配开始并找到上一个匹配的match.end()-1，直到找不到其他匹配为止。我们这样做直到找不到匹配的。对于每个匹配，我们递增cnt += 1。在

我们可以使用match.end()-1，因为每个匹配都以1开头，后跟0或更多0，然后是另一个1。所以我们知道模式只能在最后一场比赛中重新开始。在

这种方法还可以节省内存：因为在找到第一个匹配项之后，在查找下一个匹配项时，您可以简单地忘记该匹配项。findall(..)方法需要同时将所有匹配项存储在内存中。在

Answer 2

可以通过正则表达式和前瞻模式来解决重叠1的情况：

import re

def count_code33(input_string):
    return len(re.findall('10*(?=1)', input_string))

# Test section    
def test(input_string):
    print('{!r} => {}'.format(input_string, count_code33(input_string)))

test('')
test('0')
test('10')
test('1001010001')
test('1001 101 10001')
test('100110110001')
test('1111')

结果：

^{pr2}$