Образцы и блоки

Как найти самую длинную цепочку вида DOGDOGDOGD…, если последний кусок может быть неполным?

Помнить, сколько символов цепочки уже набрано: следующим должен идти pattern[current % 3]. Совпал — цепочка растёт. Не совпал — новая цепочка может начаться, только если это D. После 0, 3, 6 набранных символов снова ждём D, после 1, 4, 7 — O: остаток от деления на длину образца повторяется.

В строке ODOGDOGDORDOG цепочка DOGDOGDO обрывается на R: там ждали G. R не может начать новую цепочку — current = 0. Следующая D начинает цепочку заново.

s = 'ODOGDOGDORDOG'pattern = 'DOG'current = 0best = 0for c in s:    if c == pattern[current % 3]:        current += 1    elif c == 'D':        current = 1    else:        current = 0    best = max(best, current) print(best)

А если цепочка из групп SQRP может начинаться с любой буквы группы — RPSQRPS тоже подходит?

Тогда хватает проверки соседей: за S должна идти Q, за Q — R, за R — P, за P — S. Это условие на пару, и сброс — до 1, как в подтеме 2. Какая буква должна идти следом, удобно хранить в словаре:

s = 'QRPSQRPSQXRPS'nxt = {'S': 'Q', 'Q': 'R', 'R': 'P', 'P': 'S'}current = 1best = 1for i in range(1, len(s)):    if nxt.get(s[i - 1]) == s[i]:        current += 1    else:        current = 1    best = max(best, current) print(best)

Цепочка QRPSQRPSQ — 9 символов, X её обрывает. nxt.get('X') вернёт None — у X следующей буквы нет. Если условие требует хоть одну полную группу SQRP, она точно есть в любой цепочке из 7 и больше символов.

Бывает, что на месте буквы допустимы два символа: в слове yandex вместо a можно писать 4, вместо e — 3. Тогда для каждого места храним набор допустимых символов и проверяем c in pattern[current % 6]:

s = 'qyandqqyand3xy4q'pattern = ['y', 'a4', 'n', 'd', 'e3', 'x']current = 0best = 0for c in s:    if c in pattern[current % 6]:        current += 1    elif c == 'y':        current = 1    else:        current = 0    best = max(best, current) print(best)

Самая длинная цепочка — yand3xy4: 3 стоит на месте e, 4 — на месте a.

Сколько пар AB или CB идёт подряд? Например, в ABCBAB — три пары.

Пары не перекрываются, поэтому идём по строке шагом 2. Цепочка пар может начаться и на чётной, и на нечётной позиции — проверяем оба смещения. Третий аргумент range — шаг: range(1, 9, 2) даёт 1, 3, 5, 7.

s = 'CABCBABAB'best = 0for start in (0, 1):    current = 0    for i in range(start, len(s) - 1, 2):        if s[i:i + 2] in ('AB', 'CB'):            current += 1        else:            current = 0        best = max(best, current) print(best)

С нулевой позиции пары CA, BC, BA, BA — ни одной подходящей. С первой — AB, CB, AB, AB: четыре подряд.

Для троек вроде ABA или BAB шаг 3 и смещения три: 0, 1 и 2. Если спрашивают число символов, а не пар, ответ умножают на длину блока.

Бывает, что блок — любые символы набора: «RGB-цепочка — шесть шестнадцатеричных цифр». Тогда блоки друг от друга не отличаются, и число блоков подряд — это длина самой длинной цепочки таких символов, делённая на 6 нацело.

Сколько в строке фрагментов длины 5, которые читаются одинаково слева направо и справа налево — палиндромов?

Перебрать все начала: кусок s[i:i + 5] для i от 0 до len(s) − 5. Кусков около миллиона, но каждый короткий — это быстро. Кусок-палиндром совпадает со своим переворотом t[::-1].

s = 'ABCBAXABA'count = 0for i in range(len(s) - 4):    t = s[i:i + 5]    if t == t[::-1]:        count += 1 print(count)

Подходят ABCBA и BAXAB. Последнее начало — len(s) − 5, а правая граница range не входит, поэтому range(len(s) - 4). Так же проверяют любые условия на короткий кусок: «первый символ из A, B, C, второй из C, D, E, символы не повторяются» — это len(set(t)) == 3 и проверки по позициям.

Вхождения слова тоже ищут перебором начал. Метод count здесь не годится: найдя слово, он продолжает поиск после его конца и пропускает перекрытия.

• Образецc == pattern[current % m]
• Не совпал1, если это первая буква образца, иначе 0
• С любого местапроверка пары «за этой буквой — следующая»
• Пары, тройкишаг 2 или 3, все смещения
• Короткий кусокперебор начал: s[i:i + k]
• Перекрытияcount их не видит — перебирай начала