Разбираем олимпиадный пример и учимся базовой грамматике «регулярок»

8–9 классы • Подготовка к олимпиаде по кибербезопасности

Политики паролей описываются «масками» и регулярными выражениями.
Чтобы понять, какой пароль подходит, нужно уметь читать эти записи.

Вы научитесь:

• читать маски и регулярные выражения (Regex)
• переводить «самодельные» маски в стандартный Regex
• избегать ловушек (Unicode, «звёздочка» внутри [ ])
• быстро проверять строки и объяснять свой выбор

Маска (в задачах): набор правил, иногда с собственной семантикой символов

Маска: ID[0-9][*|!]END

Regex (регулярное выражение): стандартный язык описания шаблонов строк

^ID0-9END$

Важно: в задачах олимпиад «маска» может отличаться от стандарта Regex.

Маска: SC[a-gA-S][*|!?]OL

Правила из условия:

- Вне [ ] — символы фиксированы (SC … OL)
- [a-gA-S] — один символ: a…g или A…S
- [*|!?] — альтернация:
  - «*» = любая непустая подстрока из латинских букв/цифр
  - «!» или «?» = ровно этот символ

Итого структура строки:
SC + (одна буква из диапазона) + (либо [A-Za-z0-9]+, либо !, либо ?) + OL

1. Отметь фиксированное: SC и OL — неизменны
2. Разберись с [ ]:
   • диапазоны: a-g, A-S
   • альтернация через |
3. Уточни семантику «звёздочки» из условия (не путать со стандартным Regex)
4. Сопоставляй всю строку целиком (от начала до конца)

Варианты: SCHOOOL, SChоOL, SCHOO!L, SCHOOLOL, SCH*!OL, SCH?OL

Подумайте 30 секунд, какие подойдут.
Подсказка: проверьте позицию [a-gA-S] и затем альтернативу [*|!?].

Подходят:

• SCHOOOL — SC + H (в A–S) + OO (непустая подстрока) + OL
• SCHOOLOL — SC + H + OOL (непустая подстрока) + OL
• SCH?OL — SC + H + ? + OL

Не подходят:

• SChоOL — h не в a–g/A–S; «о» — кириллица
• SCHOO!L — «OO» заняли «*», но дальше должно идти сразу «OL», а не «!L»
• SCH*!OL — «*» как символ в строке недопустим в роли «подстроки»; «!» тогда остаётся «лишним»

Маска → Regex:

• Маска: SC[a-gA-S][*|!?]OL
• Регулярное выражение:

^SC[a-gA-S](?:[A-Za-z0-9]+|[!?])OL$

Пояснения:

• ^ … $ — требуем совпадение всей строки
• [A-Za-z0-9]+ — «непустая подстрока» из букв/цифр
• (?:X|Y) — настоящая альтернация

Строгое правило Regex:

• Внутри [ … ] всегда «один символ из множества»
• Там «|» и «*» — обычные символы, НЕ «или» и НЕ квантификатор

Если вбить маску как есть: SC[a-gA-S][|!?]OL
Regex-движок поймёт: «один символ из {, |, !, ?}» — и признает только SCH?OL.
Поэтому вначале нужно перевести «маску задачи» в корректный Regex (см. предыдущий слайд).

• Символьные классы: [abc], [a-z], [A-Za-z0-9], отрицание [^…]
• Группы и альтернация: (…|…), (?:…|…)
• Квантификаторы: ? (0 или 1), + (1+), * (0+), {m,n}
• Якоря: ^ (начало), $ (конец)
• Экранирование: . + * ? ( ) [ ] { } | ^ $ — спецсимволы

Правило №1: внутри [ … ] пишем «один символ». Повторы — квантификаторами снаружи.

• Диапазон: [a-g] = a,b,c,d,e,f,g
• Несколько диапазонов: [a-gA-S]
• Альтернация:
  • Вне класса: (cat|dog)
  • Внутри класса: [abc] — не «или-слова», а «один из символов a,b,c»

Лайфхак: когда видите «|» внутри [ … ], почти всегда это просто символ «|».

• X? — 0 или 1 раза
• X+ — 1 или более
• X* — 0 или более
• X{m,n} — от m до n

Жадность: по умолчанию берёт «как можно больше», но чтобы совпасть с остальным паттерном.
Ленивая форма: X+? и т.п. — «как можно меньше».

Похоже — не значит одинаково:

• латинская «o» (U+006F) vs кириллическая «о» (U+043E)
• визуально одинаковы, но разные коды

В задачах про пароли обычно подразумевается ASCII-латиница.
Проверяйте алфавит: [A-Za-z0-9] — только латинские буквы и цифры.

Начинается с AB,
затем одна цифра от 0 до 3,
затем ровно две латинские буквы,
заканчивается буквой Z.

Маска (олимпиадная семантика)

AB[0-3][A-Za-z][A-Za-z]Z

Регулярное выражение (стандартный Regex)

^AB[0-3][A-Za-z]{2}Z$

Какие строки подойдут?

AB2HiZ, AB3!Z, AB0abZ, AB1aZ

Подходят: AB2HiZ (2 и «Hi» — две буквы), AB0abZ (0 и «ab» — две буквы).
Не подходят:
    AB3!Z — «!» не буква.
    AB1aZ — только одна буква «a», требуется две.

Визуализация структуры: AB + [0–3] + [буква][буква] + Z

2. Составьте Regex, если пароль:

• начинается с X9
• затем 2–4 латинские буквы
• затем либо «?», либо ровно 3 цифры

Ответ: ^X9[A-Za-z]{2,4}(?:\?|[0-9]{3})$

Пример: только цифры (A=10), длина 6 → H ≈ 6·log2(10) ≈ 19.9 бит
Латиница+цифры (A≈62), длина 8 → H ≈ 8·log2(62) ≈ 47.6 бит

Вывод: длина и алфавит сильно влияют на стойкость.

import re
pat = re.compile(r'^SC[a-gA-S](?:[A-Za-z0-9]+|[!?])OL$')
tests = ["SCHOOOL","SChоOL","SCHOO!L","SCHOOLOL","SCH*!OL","SCH?OL"]
for s in tests:
    print(s, bool(pat.fullmatch(s)))

Или используйте regex101, но только после перевода маски в корректный Regex.

Что не так с Regex: SC[a-gA-S][*|!?]OL?
Ответ: внутри [ … ] «|» и «*» — не альтернация и не квантификатор, это просто символы.
Нужно: ^SC[a-gA-S](?:[A-Za-z0-9]+|[!?])OL$

• Поняли разницу между «маской из условия» и стандартным Regex
• Научились переводить маску → Regex
• Отработали диапазоны, альтернативы, квантификаторы
• Разобрали частые ловушки (Unicode, «[ ] = ровно один символ»)

Домашка:

• Придумайте 3 политики паролей и запишите их в Regex
• Для каждой — по 3 подходящих и 3 неподходящих примера с объяснениями

• Классы: [A-Za-z], [0-9], [A-Za-z0-9], [^…]
• Группы/ИЛИ: (…|…), (?:…|…)
• Квантификаторы: ?, +, *, {m,n}
• Якоря: ^, $
• Экранирование: ., +, *, ?, \(, \), \[, \], {, }, |, ^, $

Главное правило: повторы задаются квантификаторами СНАРУЖИ от [ … ],
внутри [ … ] — всегда ровно один символ из набора.