Семинар 5. Регулярные выражения
Алгоритмы и структуры данных, часть 2


Что: Семинар
Когда: Суббота, 10 марта 2018, 14:30–16:10
Где: НГУ, ауд. 2128

Описание

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

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

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

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

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

Видео