5. Regular Expression Matching
«Регулярные выражения — это либо элегантный скальпель инженера, либо граната в руках неосторожного программиста».
— Брайан Керниган
Задача о сопоставлении с регулярным выражением (Regular Expression Matching, LeetCode 10) — признанный Эверест строкового динамического программирования.
Если в предыдущих задачах символы сопоставлялись один к одному, то здесь мы моделируем фундаментальный концепт теории вычислений — недетерминированный конечный автомат (НКА / NFA) с квантификатором Клини (* — ноль или более повторений предшествующего символа) и метасимволом любого символа (.).
В бэкенде эта задача открывает понимание того, почему стандартный пакет regexp в Go гарантированно защищен от катастрофических уязвимостей ReDoS (Regular Expression Denial of Service), выводящих из строя целые кластеры на Python, Node.js или Java.
1. Постановка задачи и правила грамматики
Условие:
Даны строка s (текст) и строка p (шаблон регулярного выражения).
Реализовать функцию проверки полного совпадения строки с шаблоном со следующими правилами:
.— соответствует любому одиночному символу.*— соответствует нулю или более повторений предшествующего символа.
Вход: s = "aab", p = "c*a*b"
Выход: true
Пояснение: 'c*' берется 0 раз (""), 'a*' берется 2 раза ("aa"), 'b' совпадает с 'b'. Итог: "aab".
2. Логика переходов: Моделирование состояний автомата
Определим состояние:
$dp[i][j]$ — истинно, если префикс строки $s[0 \dots i-1]$ полностью матчится префиксом паттерна $p[0 \dots j-1]$.
При вычислении ячейки $(i, j)$ смотрим на символ паттерна $p[j-1]$:
Сценарий 1: Обычный символ или точка (p[j-1] != '*')
Символ паттерна сопоставляется ровно с одним символом строки:
$$dp[i][j] = dp[i-1][j-1] \quad \text{при условии, что} \quad (p[j-1] == s[i-1] \lor p[j-1] == '.')$$
Сценарий 2: Квантификатор звездочка (p[j-1] == '*')
Символ * никогда не стоит сам по себе — он модифицирует предшествующий символ $p[j-2]$.
Перед нами две альтернативы:
- Ноль вхождений (Zero occurrences):
Мы полностью игнорируем блок $p[j-2] \ p[j-1]$ (например,c*превращается в пустую строку). Значение берется на 2 шага назад по паттерну:
$$dp[i][j-2]$$ - Одно или более вхождений (Consume one character):
Если символ $p[j-2]$ совпадает с текущим символом строки $s[i-1]$ (или $p[j-2] == '.'$), мы «поглощаем» символ строки $s[i-1]$, но оставляем паттерн на месте, так как*может поглотить следующий символ:
$$dp[i-1][j]$$
Итоговая дизъюнкция для *:
$$dp[i][j] = dp[i][j-2] \;\lor\; \Big((p[j-2] == s[i-1] \lor p[j-2] == '.') \land dp[i-1][j]\Big)$$
flowchart TD
classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
classDef success fill:#064e3b,stroke:#34d399,stroke-width:2px,color:#f8fafc
classDef error fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
classDef entry fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
Check{"Символ p[j-1] == '*'?"}:::warning
Check -- "Нет (Символ или точка)" --> CharMatch{"p[j-1] == s[i-1]<br/>или p[j-1] == '.'?"}:::process
CharMatch -- "Да" --> Diag["dp[i][j] = dp[i-1][j-1]<br/>(Диагональный шаг)"]:::success
CharMatch -- "Нет" --> False1["dp[i][j] = false"]:::error
Check -- "Да (Звездочка)" --> ZeroOcc["1. Ноль вхождений:<br/>dp[i][j-2] (срез без X*)"]:::process
ZeroOcc --> StarMatch{"2. Одно+ вхождений:<br/>p[j-2] совпал с s[i-1]?"}:::process
StarMatch -- "Да" --> Consume["ИЛИ dp[i-1][j]<br/>(Съедаем символ из s)"]:::success
StarMatch -- "Нет" --> OnlyZero["Остается только dp[i][j-2]"]:::process
3. Идиоматичная реализация на Go 1.22+ ($O(N)$ памяти)
Так как текущая строка $i$ зависит только от значений в этой же строке со смещением назад ($dp[i][j-2]$) и от значений в предыдущей строке ($dp[i-1][j]$ и $dp[i-1][j-1]$), мы используем два чередующихся среза: prev и curr.
package regex
// IsMatch проверяет полное соответствие строки s шаблону p с поддержкой '.' и '*'.
// Временная сложность: O(M * N).
// Пространственная сложность: O(N) — два компактных булевых среза длины len(p)+1.
func IsMatch(s string, p string) bool {
m, n := len(s), len(p)
prev := make([]bool, n+1)
curr := make([]bool, n+1)
// База: пустая строка s полностью совпадает с пустым шаблоном p
prev[0] = true
// База для пустой строки: шаблоны вида a*, a*b*, a*b*c* могут свернуться в пустую строку
for j := 2; j <= n; j++ {
if p[j-1] == '*' {
prev[j] = prev[j-2]
}
}
for i := 1; i <= m; i++ {
// Непустая строка не может совпасть с пустым паттерном
curr[0] = false
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
// Вариант 1: ноль повторений (игнорируем блок p[j-2..j-1])
curr[j] = curr[j-2]
// Вариант 2: одно или более повторений
if p[j-2] == '.' || p[j-2] == s[i-1] {
curr[j] = curr[j] || prev[j]
}
} else {
// Одиночный символ или точка
if p[j-1] == '.' || p[j-1] == s[i-1] {
curr[j] = prev[j-1]
} else {
curr[j] = false
}
}
}
// Swap срезов: смена поколений без дополнительных аллокаций
prev, curr = curr, prev
}
return prev[n]
}
4. System Design: Архитектура RE2 против PCRE и угроза ReDoS
Почему знание этого алгоритма обязательно для Senior Backend инженера?
Большинство языков программирования (Python re, JavaScript RegExp, PHP, Perl, Ruby) используют для регулярных выражений движки на основе обратного слежения (Backtracking / PCRE).
Если пользователь отправляет строку:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaa!
на паттерн вида (a+)+$, движок начинает экспоненциальный перебор всех возможных группировок.
Сложность взлетает до $O(2^N)$! Одно невинное регулярное выражение подвешивает CPU ядра на часы — сервис падает с отказом в обслуживании (уязвимость ReDoS — Regular Expression Denial of Service).
flowchart LR
classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
classDef success fill:#064e3b,stroke:#34d399,stroke-width:2px,color:#f8fafc
classDef error fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
classDef entry fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
Input["Входные данные:<br/>'(a+)+$' на 'aaaaa!'"]:::entry
Input --> PCRE["PCRE / Backtracking (Python, JS):<br/>Экспоненциальный взрыв O(2^N)"]:::error
Input --> RE2["RE2 / Thompson NFA (Go standard library):<br/>Гарантированное линейное время O(M * N)"]:::success
PCRE --> ReDoS["💥 ReDoS: 100% CPU, падение сервиса"]:::error
RE2 --> Safe["✅ Безопасно: предсказуемое время ответа"]:::success
Почему Go не подвержен ReDoS?
Стандартный пакет regexp в Go построен на библиотеке RE2 (созданной Робом Пайком и Кеном Томпсоном в Google).
В ее основе лежит алгоритм Томпсона (Thompson NFA Construction, 1968 г.), который моделирует состояния параллельно — в точности так же, как наше DP!
Время работы регулярных выражений в Go строго ограничено $O(M \cdot N)$. Никакой злоумышленник не может положить ваш сервис каверзным вводом.
5. Вопросы для собеседования
Итог
- Модель NFA: Квантификатор
*ветвит состояние на пропуск двух символов паттерна (curr[j-2]) или поглощение символа строки (prev[j]). - Своп срезов: Использование пары
prevиcurrисключает аллокации в куче на каждом шаге цикла. - ReDoS иммунитет: Алгоритм работает с гарантированной сложностью $O(M \cdot N)$, что объясняет фундаментальную надежность пакета
regexpв Go.
В следующей финальной лекции кластера строкового DP мы разберем задачу о сопоставлении с масками файлов (Glob / Wildcard): 6. Wildcard Matching.