Python - Substrings, die nur 'a', 'b' oder 'c'

Question

I enthielt, wurde für die Codierung this problem.

Maggu hat gerade Spiel-Schule verbunden. Sein Lehrer brachte ihm A, A, B, B, C, C bei. Er ist sehr fasziniert von diesen Briefen und nun sucht er nur nach den Fäden, die nur diese Buchstaben enthalten. Aber wie gesagt, er ist ein kleiner Typ, er kann die Anzahl solcher Teilstrings nicht alleine berechnen. Finde die Anzahl solcher 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) 

erkannte ich, dass wir das Problem Fall zu senken, reduzieren kann. Ich habe den Code geschrieben, aber es ist nicht effizient für große Strings. Und im Großen Sinne meine ich außergewöhnlich große Saiten. Ich habe erkannt, dass es die substrings Funktion ist, die viel Zeit in Anspruch nimmt. Wie kann ich den Zeitaufwand der substrings Funktion reduzieren? Kann ich es durch einen anderen Code ersetzen?

Danke.

Answer 1

Der Grund, warum dies exponentiell ist, liegt darin, dass Sie für verschiedene Fensterlängen (bis zu len (string)) über denselben String iterieren. Dies ist ein Job für reguläre Ausdrücke, der einfach einen Durchlauf über Ihre Zeichenfolge ausführt, um alle Folgen zu finden, die die Buchstaben a, b, c, A, B und C nacheinander mindestens einmal enthalten.

Nachdem Sie diese Sequenzen gefunden haben, können Sie ihre arithmetische Progression berechnen, um zu zählen, wie viele Teilstrings jeweils enthalten sind. Um zu verstehen, warum wir die arithmetische Progression verwenden müssen, müssen wir die Sequenz 'abc' irgendwo in der großen Zeichenkette finden. Die eigentlichen Teilstrings dieser Sequenz sind 'a', 'ab', 'abc', 'b', 'bc' und 'c'. Für einen String der Länge n können wir n Teilstrings beginnend mit dem ersten Buchstaben, n-1 Teilstrings beginnend mit dem zweiten Buchstaben, ... und 1 Teilstring beginnend mit dem letzten Buchstaben konstruieren.

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 

Für das Beispiel in der Verbindung gezeigt

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

2 
6 
4 
21 
0 

---

Wenn Sie implementieren möchten, was re.findall() tut selbst, erhalten Sie folgende ausprobieren können.

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)