只包含“a”、“b”或“c”的python子字符串

Question

我在为this problem.编写代码

Maggu has just joined play school. His teacher taught him A,a,B,b,C,c. He is much fascinated with these letters and now he is looking only for those strings which contains these letters only. But as i said he is a little guy he cant calculate the number of such sub-strings alone. Find the number of such strings.

def substrings(string):
    for size in range(1, len(string)+1):
        for index in range(len(string)-size+1):
            yield string[index:index+size]

l = []

for x in range(int(raw_input())):
    l.append(raw_input().lower())

not_ = 'defghijklmnopqrstuvwxyz'

for string in l:
    count = 0
    for substr in substrings(string):
        if all(letter not in substr for letter in not_):
            count = count + 1
    print(count)

我意识到我们可以把问题简化为小写。我已经编写了代码，但对于大字符串来说，它不是有效的。我指的是非常大的弦。我意识到这个功能占用了很多时间。如何减少substrings函数的时间消耗？我可以用其他代码替换它吗？

谢谢。

Answer 1

之所以是指数型的，是因为您在同一个字符串上迭代不同的窗口长度（直到len（string））。这是一个正则表达式的工作，它只需对字符串进行一次遍历，以查找至少一次连续包含字母a、b、c、a、b和c的任何序列。在

找到这些序列后，可以计算它们的算术级数，以计算每个序列包含的子字符串数。为了理解为什么我们必须使用算术级数，假设我们在大字符串的某个地方找到了序列'abc'。此序列的实际子字符串是“a”、“ab”、“abc”、“b”、“bc”和“c”。基本上，对于长度为n的字符串，我们可以构造从第一个字母开始的n个子字符串，从第二个字母开始的n-1个子字符串，…，以及从最后一个字母开始的1个子字符串。在

import re

def count_substrings(string):
    found = re.findall('[a-cA-C]+', string)
    count = 0
    for f in found:
        length = len(f)
        count += length * (length + 1) / 2
    return count

对于链接中显示的示例

^{pr2}$

---

如果您想实现re.findall()自己的功能，可以尝试以下操作。在

found = []
substring = ''
for s in string:
    if s in 'abcABC':
        substring += s
    else:
        # if we had a sequence going, it just ended, so add it to our found list
        if substring:
            found.append(substring)
            substring = ''
# make sure to append the last sequence we had been working on
if substring:
    found.append(substring)