zeichenfolgenanzahl mit überlappenden Vorkommen

>>> import re
>>> text = '1011101111'
>>> len(re.findall('(?=11)', text))
5

Wenn Sie nicht die gesamte Liste der Übereinstimmungen in den Speicher laden möchten, wäre dies niemals ein Problem! Sie könnten dies tun, wenn Sie wirklich wollten:

>>> sum(1 for _ in re.finditer('(?=11)', text))
5

Als Funktion (re.escape stellt sicher, dass die Teilzeichenfolge den regulären Ausdruck nicht beeinträchtigt):

>>> def occurrences(text, sub):
        return len(re.findall('(?={0})'.format(re.escape(sub)), text))

>>> occurrences(text, '11')
5

Sie können auch das neue Python-Regex-Modul verwenden, das überlappende Übereinstimmungen unterstützt.

import regex as re

def count_overlapping(text, search_for):
    return len(re.findall(search_for, text, overlapped=True))

count_overlapping('1011101111','11')  # 5

str.count von Python zählt nicht überlappende Teilzeichenfolgen:

In [3]: "ababa".count("aba")
Out[3]: 1

Hier sind ein paar Möglichkeiten, überlappende Sequenzen zu zählen. Ich bin mir sicher, dass es noch mehr gibt :)

Vorausschauende reguläre Ausdrücke

Wie finde ich überlappende Übereinstimmungen mit einem Regex?

In [10]: re.findall("a(?=ba)", "ababa")
Out[10]: ['a', 'a']

Generieren Sie alle Teilzeichenfolgen

In [11]: data = "ababa"
In [17]: sum(1 for i in range(len(data)) if data.startswith("aba", i))
Out[17]: 2

s = "bobobob"
sub = "bob"
ln = len(sub)
print(sum(sub == s[i:i+ln] for i in xrange(len(s)-(ln-1))))

So finden Sie ein Muster in einer anderen Zeichenfolge mit Überlappung

Diese Funktion (eine andere Lösung!) Erhält ein Muster und einen Text. Gibt eine Liste mit allen untergeordneten Zeichenfolgen und deren Positionen zurück.

def occurrences(pattern, text):
    """
    input: search a pattern (regular expression) in a text
    returns: a list of substrings and their positions 
    """
    p = re.compile('(?=({0}))'.format(pattern))
    matches = re.finditer(p, text)
    return [(match.group(1), match.start()) for match in matches]

print (occurrences('ana', 'banana'))
print (occurrences('.ana', 'Banana-fana fo-fana'))

[('ana', 1), ('ana', 3)] 
[('Bana', 0), ('Nana', 2), ('Fana', 7), ('Fana', 15)]

def count_substring(string, sub_string):
    count = 0
    for pos in range(len(string)):
        if string[pos:].startswith(sub_string):
            count += 1
    return count

Dies könnte der einfachste Weg sein.

Meine Antwort auf die Bob-Frage zum Kurs:

s = 'azcbobobegghaklbob'
total = 0
for i in range(len(s)-2):
    if s[i:i+3] == 'bob':
        total += 1
print 'number of times bob occurs is: ', total

Ein ziemlich pythonischer Weg wäre, Listenverständnis hier zu verwenden, obwohl es wahrscheinlich nicht der effizienteste wäre.

sequence = 'abaaadcaaaa'
substr = 'aa'

counts = sum([
    sequence.startswith(sub, i) for i in range(len(sequence))
])
print(counts)  # 5

Die Liste wäre [False, False, True, False, False, False, True, True, False, False], da alle Indizes durch die Zeichenfolge geprüft werden, und weil int(True) == 1, sum die Gesamtzahl der Übereinstimmungen angibt.

def count_substring(string, sub_string):
    counter = 0
    for i in range(len(string)):
        if string[i:].startswith(sub_string):
        counter = counter + 1
    return counter

Der obige Code durchläuft einfach einmal den gesamten String und prüft ständig, ob ein String mit dem bestimmten Teilstring beginnt, der gerade gezählt wird.

Hier ist mein edX MIT "find bob" * -Lösung (* find Anzahl von "bob" -Ereignissen in einem String mit dem Namen s), der in der Regel überlappende Vorkommen einer gegebenen Unterstufe zählt:

s = 'azcbobobegghakl'
count = 0

while 'bob' in s:
    count += 1 
    s = s[(s.find('bob') + 2):]

print "Number of times bob occurs is: {}".format(count)

Das kann mit Regex gelöst werden.

import re
def function(string, sub_string):
    match = re.findall('(?='+sub_string+')',string)
    return len(match)

Wenn die Zeichenfolgen groß sind, möchten Sie Rabin-Karp verwenden, zusammenfassend:

• ein rollendes Fenster mit der Größe eines Teilstrings, das sich über einem String bewegt
• ein Hash mit O(1) Overhead zum Hinzufügen und Entfernen (d. h. Verschieben um 1 Zeichen)
• in C implementiert oder auf Pypy angewiesen

Dies ist ein weiteres Beispiel für die Verwendung von str.find(), aber viele Antworten machen es komplizierter als nötig:

def occurrences(text, sub):
    c, n = 0, text.find(sub)
    while n != -1:
        c += 1
        n = text.find(sub, n+1)
    return c

In []:
occurrences('1011101111', '11')

Out[]:
5

Eine einfache Möglichkeit, das Auftreten von Teilzeichenfolgen zu zählen, ist die Verwendung von count():

>>> s = 'bobob'
>>> s.count('bob')
1

Sie können replace () verwenden, um überlappende Zeichenfolgen zu finden, wenn Sie wissen, welcher Teil überlappt:

>>> s = 'bobob'
>>> s.replace('b', 'bb').count('bob')
2

Beachten Sie, dass es nicht nur statische, sondern auch andere Einschränkungen gibt:

>>> s = 'aaa'
>>> count('aa') # there must be two occurrences
1 
>>> s.replace('a', 'aa').count('aa')
3

Gegeben

sequence = '1011101111'
sub = "11"

Code

In diesem speziellen Fall

sum(x == Tuple(sub) for x in Zip(sequence, sequence[1:]))
# 5

Ganz allgemein dies

windows = Zip(*([sequence[i:] for i, _ in enumerate(sequence)][:len(sub)]))
sum(x == Tuple(sub) for x in windows)
# 5

oder auf Generatoren erweitern:

import itertools as it


iter_ = (sequence[i:] for i, _ in enumerate(sequence))
windows = Zip(*(it.islice(iter_, None, len(sub))))
sum(x == Tuple(sub) for x in windows)

Alternative

Sie können more_itertools.locate verwenden:

import more_itertools as mit


len(list(mit.locate(sequence, pred=lambda *args: args == Tuple(sub), window_size=len(sub))))
# 5

Funktion, die als Eingabe zwei Zeichenfolgen übernimmt und zählt, wie oft ein Teil in Zeichenfolgen auftritt, einschließlich Überlappungen. Um zu prüfen, ob Sub eine Unterzeichenfolge ist, habe ich den Operator in verwendet. 

def count_Occurrences(string, sub):
    count=0
    for i in range(0, len(string)-len(sub)+1):
        if sub in string[i:i+len(sub)]:
            count=count+1
    print 'Number of times sub occurs in string (including overlaps): ', count

Für eine duplizierte question habe ich mich entschieden, sie 3 mal 3 zu zählen und die Zeichenfolge zu vergleichen, z.

counted = 0

for i in range(len(string)):

    if string[i*3:(i+1)*3] == 'xox':
       counted = counted +1

print counted

def count_overlaps (string, look_for):
    start   = 0
    matches = 0

    while True:
        start = string.find (look_for, start)
        if start < 0:
            break

        start   += 1
        matches += 1

    return matches

print count_overlaps ('abrabra', 'abra')

Eine Alternative, die der akzeptierten Antwort sehr nahe kommt, jedoch while als if-Test verwendet, anstatt if in die Schleife einzufügen:

def countSubstr(string, sub):
    count = 0
    while sub in string:
        count += 1
        string = string[string.find(sub) + 1:]
    return count;

Dies vermeidet while True: und ist meiner Meinung nach ein wenig sauberer