01 Что такое конечный автомат?
Конечный автомат (КА) — это абстрактная модель, которая читает символы один за другим и меняет своё состояние по определённым правилам. Представьте робота, который ходит между комнатами: в каждой комнате он ждёт определённую букву, и если видит её — переходит в следующую комнату.
Компоненты автомата
Состояния — «комнаты», в которых может быть автомат
Алфавит — символы, которые он читает
Переходы — правила: «если в состоянии X увидел символ Y → перейди в Z»
Начальное состояние — откуда стартуем
Зачем это нужно?
Искать циклические паттерны (ABAB...)
Проверять корректность последовательности
Считать длину подстроки, удовлетворяющей условию
Делать это за один проход — O(n)
02 Задача: паттерн ABAB...
Найти максимальную длину подстроки, которая является повторением паттерна AB. Например, в строке XABABACAB самая длинная такая подстрока — ABABA (длина 5).
Два состояния и диаграмма переходов
Для паттерна AB автомату нужно всего два состояния:
'A' 'B'
┌──────────┐ ┌──────────┐
│ │ │ │
▼ │ ▼ │
┌───┐ 'A' ┌───┐ 'B' ┌───┐
│ 0 │ ────► │ 1 │ ────► │ 0 │ (цикл)
└───┘ └───┘ └───┘
│ │
│ 'B' │ 'A'
▼ ▼
СБРОС СБРОС
(len=0) (проверка нового начала)
⚠️ Умный сброс При несовпадении автомат не просто обнуляется — он проверяет, не является ли текущий символ началом нового паттерна. Например, если ждали B, а пришла A — это новое начало!
03 Симулятор автомата
Введите строку и паттерн, затем нажимайте «Шаг» или «Запустить», чтобы пошагово увидеть, как автомат обрабатывает каждый символ.
Попробуй · интерактивный симулятор
Нажми «Шаг» или «Запустить», чтобы начать
04 Трассировка на примере
Разберём строку XABABAC с паттерном AB по шагам:
| Символ |
Ожидали |
Действие |
cur_len |
max_len |
X |
A |
X ≠ A → сброс |
0 |
0 |
A |
A |
✅ совпал → длина +1 |
1 |
0 |
B |
B |
✅ совпал → длина +1 |
2 |
0 |
A |
A |
✅ совпал → длина +1 |
3 |
0 |
B |
B |
✅ совпал → длина +1 |
4 |
0 |
A |
A |
✅ совпал → длина +1 |
5 |
0 |
C |
B |
C ≠ B → сохраняем 5, сброс |
0 |
5 |
✅ Результат: max_len = 5 Подстрока ABABA — это 5 символов. Обратите внимание: она не обязана заканчиваться полным повторением паттерна!
05 Универсальный шаблон
Для любого циклического паттерна (AB, XYZ, ABCD...) используем одну формулу: ожидаемый символ — это pattern[cur_len % len(pattern)].
def max_pattern_length(s, pattern):
"""Поиск максимальной длины циклического паттерна в строке."""
cur_len = 0
max_len = 0
n = len(pattern)
for c in s:
# Какой символ ожидаем на текущей позиции?
expected = pattern[cur_len % n]
if c == expected:
cur_len += 1 # ✅ Совпал → удлиняем
else:
max_len = max(max_len, cur_len)
if c == pattern[0]:
cur_len = 1 # 🔄 Начало нового паттерна
else:
cur_len = 0 # ❌ Полный сброс
return max(max_len, cur_len)
Ключевые идеи алгоритма
Один проход
Проходим строку слева направо один раз. Сложность O(n).
Формула ожидания
expected = pattern[cur_len % n] — работает для любого паттерна.
Умный сброс
При несовпадении: если символ = начало паттерна → cur_len = 1, иначе 0.
Два счётчика
cur_len — текущая цепочка, max_len — лучший результат. В конце: max(max_len, cur_len).
Шпаргалка
| Элемент |
Описание |
state |
Текущее состояние автомата (позиция в паттерне) |
cur_len |
Длина текущей найденной цепочки |
max_len |
Максимальная длина, найденная за весь проход |
pattern[cur_len % n] |
Ожидаемый символ на текущей позиции |
| Умный сброс |
Если символ = pattern[0] → cur_len = 1, иначе 0 |
| Финал |
max(max_len, cur_len) — не забыть! |