В 2022 году Computer Science Center приостановил набор и обучение
Курсы
/
Алгоритмы и структуры данных, часть 2
/
весна 2020
/

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

Суббота, 14 марта 2020
НГУ, ауд. 4259, НГУ, новый корпус
Список тем / 16 записей
    1.
    Лекция 1. Строки. Z-функция
    2.
    Семинар 1. LCP, поиск палиндромов, ДКА
    3.
    Лекция 2. Префикс-функция, поиск бора
    4.
    Семинар 2. Поиск тандемных повторов, Ахо-Корасик
    5.
    Лекция 3. Суффиксное дерево
    6.
    Семинар 3. Эквивалентность автоматов
    7.
    Лекция 4. Суффиксный массив
    8.
    Семинар 4. Недетерминированные автоматы
    9.
    Лекция 5. Суффиксный массив (продолжение)
    10.
    Семинар 5. Регулярные выражения
    11.
    Лекция 6. Преобразование Барроуза-Уилера
    12.
    Семинар 6. Контекстно-свободные грамматики
    13.
    Лекция 7. Приближённый поиск подстроки
    14.
    Семинар 7. Контекстно-свободные грамматики
    15.
    Лекция 8. Графы, обход в ширину, обход в глубину
    16.
    Семинар 8. Разбор КС-грамматики

Описание

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

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

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

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

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