найти наибольшее количество раз подряд подстрока появляется в строке - PullRequest
Новая
       22

найти наибольшее количество раз подряд подстрока появляется в строке

2 голосов
/ 25 октября 2019

У меня длинная строка символов, и я не только пытаюсь выяснить, существует ли подстрока этих символов в большей строке, я также пытаюсь найти самый длинный ряд последовательных экземпляров.

Например ... в приведенном ниже фрагменте кода я обнаружил, что могу использовать "count", чтобы увидеть, сколько раз подстрока b появляется в a. Этот результат равен 5. Однако я пытаюсь определить самый длинный последовательный прогон, который будет равен 3 (где «abc» появляется спина к спине посередине). Я испытываю трудности в прохождении логики этого. Любой совет будет оценен. 

a = "abcxyzabcabcabcxyzabcxyz"

b = "abc"

total = a.count(b)

print(total)

Ответы [ 4 ]

1 голос
/ 25 октября 2019

Это должно быть довольно просто с циклом while: 

def func(a, b): 
    n = 1 
    while b*n in a: 
        n += 1 
    return n - 1
0 голосов
/ 25 октября 2019

Вы можете использовать re.findall с шаблоном, который соответствует одному или нескольким разам b (используйте re.escape, чтобы предотвратить интерпретацию b как регулярное выражение), затем сопоставьте возвращаемые строки с len и передайтеих на max, чтобы получить длину самого длинного совпадения, а затем разделить эту длину на длину b, чтобы получить количество повторений b: 

import re
max(map(len, re.findall('(?:%s)+' % re.escape(b), a))) // len(b)
0 голосов
/ 25 октября 2019

Продолжайте звонить a.index на b с соответствующими индексами. Если индекс является началом вашего подмножества, вы в том же прогоне. В противном случае начните новый прогон: 

def longest_run(string, pattern):
    longest = 0
    current = 0
    start = 0
    while True:
        try:
            ind = string.index(pattern, start)
            if ind == start:
                current += 1
            else:
                if current > longest:
                    longest = current
                current = 1
            start += len(pattern)
        except ValueError:
            return longest
0 голосов
/ 25 октября 2019

Одним из возможных и наивных решений является использование функции python index для определения ближайшего индекса подстроки. Оттуда вы можете просто продолжить поиск подстроки, пока не найдете точку, в которой она больше не появляется, а затем снова вызвать index, чтобы пропустить.

Пример: 

a = "abcxyzabcabcabcxyzabcxyz"
b = "abc"

curr_index = a.index(b)
longest_count = 0
current_count = 0

while curr_index < len(a):
    if a[curr_index : curr_index + len(b)] == b:
        curr_index += len(b)
        current_count += 1
    else:
        if longest_count < current_count:
            longest_count = current_count
        try:
            curr_index = a.index(b, curr_index)
        except ValueError:
            # Substring no longer found in string slice
            break
        current_count = 0

if longest_count < current_count:
    longest_count = current_count

print(longest_count)

Thisпросто возвращает самый длинный повторяющийся отсчет, но не возвращает место, где он начинается. Однако добавить эту функциональность тривиально.

...