のpython - 唯一の 'A'、 'B' または

Question

私はthis problem.

Magguをコードして 'C' を含んでサブストリングはただの遊びスクールに参加しています。彼の教師は彼にA、a、B、b、C、cを教えました。彼はこれらの手紙に非常に魅了され、今ではこれらの文字のみを含む文字列を探しています。しかし、私は彼が小さな男だと言ったので、そのようなサブストリングの数だけを計算することはできません。そのような文字列の数を探します。

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機能であることに気づいた。 substrings機能の時間消費をどのように減らすことができますか？他のコードで置き換えることはできますか？

ありがとうございました。

Answer 1

これが指数関数的であるのは、同じ文字列に対して、異なるウィンドウの長さ（最大len（文字列））を反復するためです。これは正規表現の仕事です。文字列を1回通過させるだけで、文字a、b、c、A、B、Cを少なくとも1回連続して検索します。

これらのシーケンスが見つかったら、算術の進行を計算して、それらに含まれている部分文字列の数を数えます。なぜ算術演算を使用しなければならないのか理解するためには、大きな文字列のどこかにシーケンス 'abc'があると考えてください。このシーケンスの実際の部分文字列は、 'a'、 'ab'、 'abc'、 'b'、 'bc'、および 'c'です。基本的に、長さnの文字列に対して、最初の文字から始まるn個の部分文字列、2番目の文字から始まるn-1個の部分文字列、...、最後の文字から始まる1個の部分文字列を構築することができます。あなたはre.findall()自身が何を実装したい場合は、以下のことを試すことができ、リンク

>>> strings = ['AXa', 'ABC', 'AXBC', 'AaBbCc', 'XxYyZz'] 
>>> for s in strings: 
... print(count_substrings(s)) 

2 
6 
4 
21 
0 

---

に示す例

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 

。