piton - sadece 'a', 'b' veya

Question

Ben this problem.

Maggu için kodlama edildi 'c' ihtiva Altdizgelerin sadece play okulu katıldı. Öğretmeni ona A, a, B, b, C, c. Bu mektuplardan çok etkileniyor ve şimdi sadece bu harfleri içeren dizelere bakıyor. Ama küçük bir adam olduğunu söylediğim gibi, bu tür alt dizilerin sayısını tek başına hesaplayamaz. Bu dizelerin sayısını bulun.

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) 

Bence harfe sorunu azaltabilir fark etti. Kodu yazdım ama geniş dizeler için etkili değil. Ve büyük ölçüde son derece geniş dizeleri kastediyorum. Çok zaman harcayan substrings işlevinin olduğunu fark ettim. substrings işlevinin zaman tüketimini nasıl azaltabilirim? Başka bir kodla değiştirebilir miyim?

Teşekkürler.

Answer 1

Bunun neden üstel olduğu nedeni, farklı pencere uzunlukları için aynı dizgiyi (len (string) değerine kadar) yinelemenizdir. Bu, düzenli ifadeler için bir iştir, bu sadece dizginizin üzerine bir geçiş yaparak a, b, c, A, B ve C harflerini en az bir kez ardışık olarak içeren dizileri bulmaktır.

Bu dizileri bulduktan sonra, bunların her birinin kaç tane alt dizesini saymak için aritmetik ilerlemesini hesaplayabilirsiniz. Neden aritmetik ilerlemeyi kullanmak zorunda olduğumuzu anlamak için, büyük dizgede bir yerde 'abc' dizisini bulduk. Bu dizinin asıl alt dizeleri 'a', 'ab', 'abc', 'b', 'bc' ve 'c' şeklindedir. Temel olarak, n uzunluğundaki bir dizgi için, ilk harften başlayarak n-1 alt dizeleri, ikinci harften başlayarak n-1 alt dizileri, ... ve son harften başlayarak 1 alt dizgi oluşturabiliriz. Eğer re.findall() Kendini ne, aşağıdakileri deneyebilirsiniz uygulamak istiyorsanız linke

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

2 
6 
4 
21 
0 

---

gösterilen Örneğin

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 

.

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)