Что спрашивают

В строке из A, B, C нужно посчитать все вхождения комбинации ABABA, в том числе пересекающиеся. Например, конец одного вхождения может одновременно входить в начало следующего.

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

Приём решения

Переберём все возможные позиции начала i. Если от этой позиции строка начинается с ABABA, увеличим счётчик. Следующим началом всегда будет i + 1, независимо от успеха проверки.

  1. Сохраните комбинацию в pattern.
  2. Переберите range(len(s) - len(pattern) + 1).
  3. Проверьте s.startswith(pattern, i) и прибавьте единицу при совпадении.

Последнее допустимое начало равно len(s) - len(pattern) и обязательно входит в перебор. Если строка короче комбинации, range пуст и ответ нулевой; дополнительная обработка границ не нужна.

Обычный s.count(pattern) считает непересекающиеся совпадения. Перемещение сразу на длину найденного слова тоже потеряет пересечения. Проверка всех начал соответствует определению каждого отдельного вхождения.

Комбинация состоит из пяти символов, поэтому каждая проверка ограничена постоянной длиной. Время — O(n), дополнительная память — O(1). Для очень длинного переменного образца можно изучить префикс-функцию и алгоритм КМП; для фиксированной ABABA достаточно простого прохода.

Разбор на примере

Ввод

CABABABABAC

Вывод

3
Разбор примера по шагам
Начало с нуляФрагментЧисло найденных
1ABABA1
3ABABA2
5ABABA3

Внутри строки стоит ABABABABA. Вхождения начинаются на позициях 1, 3 и 5 исходной строки, используя общие символы. Проверка каждого начала находит все три. Переход сразу за конец первого совпадения пропустил бы часть из них.

Код на Python и C++

На каждом шаге старт увеличивается на единицу. startswith проверяет комбинацию с заданного индекса, не создавая среза всей оставшейся строки.

В C++ у строки нет метода, считающего вхождения подстроки, поэтому цикл по стартам — обычное решение. Проверку с позиции делает s.compare(start, 5, pattern) == 0.

import sys


def solve(s):
    pattern = 'ABABA'
    answer = 0
    for start in range(len(s) - len(pattern) + 1):
        if s.startswith(pattern, start):
            answer += 1
    return answer

if __name__ == '__main__':
    print(solve(sys.stdin.readline().rstrip('\r\n')))
#include <iostream>
#include <string>
using namespace std;

int solve(const string& s) {
    const string pattern = "ABABA";
    int n = s.size(), len = pattern.size();
    int answer = 0;
    for (int start = 0; start + len <= n; start++) {
        if (s.compare(start, len, pattern) == 0)
            answer += 1;
    }
    return answer;
}

int main() {
    string s;
    getline(cin, s);
    if (!s.empty() && s.back() == '\r')
        s.pop_back();
    cout << solve(s) << endl;
}

Типичные ошибки

  • Использовать count без учёта пересечений

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

  • Не включить последнее допустимое начало

    Правая граница range не входит в перебор. Прибавление единицы позволяет учесть комбинацию, заканчивающуюся на последнем символе.

  • Перебирать все длины подстрок

    Длина искомой комбинации уже известна. Для каждого начала проверяется ровно один фрагмент.