Семинар 5. Регулярные выражения

Задача поиска максимальной общей подстроки (продолжение). Решение с суффиксным массивом: смотрим LCP соседей разного типа. (LCP-массив, LCP суффиксов в виде минимума).

Регулярные языки и выражения. Пример: целые числа.

Построение эквивалентного eps-НКА по регулярному выражению. Эффективность: линейное время, линейный размер вывода. Построение регулярного выражения по eps-НКА. Связь расп. слов с путями в графе. Запись методом динамического программирования R(i, j, k). Рег. выр. для языка автомата. Неэффективность построения.

Замкнутость рег. языков относительно: теоретико-множественных операций, операций рег. выр., разворота.

Практическое использование регулярных выражений. Утилита grep: стандартное использование. Построчный ввод, проверка наличия подстроки. Алгоритмы: полиномиальный через перевод в eps-НКА (Д/З) и экспоненциальный (перебор с отсечениями). Синтаксис регулярных выражений: обычные символы, унарные операции (*/+/?), или, точка, символы начала-конца строки, квадратные скобки (диапазон, исключение), встроенные классы, экранирование. Группы.