Алгоритмы и структуры данных

18.Б13-мм группа

Дмитрий Мордвинов


Задачи

Домашняя работа 2. 12.09.19
  1. Антимат по Ахо-Корасику

    a. (3 балла) Дан текст и список нецензурных слов. Найти все вхождения нецензурных слов в тексте.
    b. (10 баллов) Напишите расширение для Вашего любимого браузера, которое фильтрует все нецензурные слова на веб-странице.

  2. Кратчайшая строка по словарю (3 балла)

    Дан словарь. Построить кратчайшую строку, в которую входят все слова словаря.

  3. Сравнение версий файлов (3-7 баллов)

    Напишите свою реализацию утилиты diff

Домашняя работа 1. 12.09.19
  1. Количество подстрок (2 балла)

    Дан текст. Посчитать количество его различных подстрок

  2. Поиск с ошибками (3 балла)

    Дан текст и строка, введённая пользователем. Найти все вхождения строки в текст с учётом, что пользователь мог ошибиться в одном символе (потерять, вставить или заменить один символ в строке).

  3. Период строки (2 балла)

    Строка называется k-периодичной, если она имеет вид α . . . α, где |α| = k. Например, строка abababab 2-периодична, 4-периодична и 8-периодична. Определите минимальный период заданной строки.

  4. Регулярные выражения (5-8 баллов)

    Напишите интерпретатор регулярных выражений

  5. Замкнутость регулярных (1 балл)

    Докажите, что класс регулярных языков замкнут относительно пересечения, дополнения и разности

  6. Сопоставление строк

    Пусть даны строки α1, . . . , αn, β1, . . . , βn ∈ Σ*.
    a. (4 балла) Найти такие i1, . . . , ik , j1, . . . , jm ∈ N, что αi1. . . αik = βj1. . . βjm, либо определить, что их не существует. Например, для α1 = a, β1 = aa подойдёт ответ i1 = 1, i2 = 1, j1 = 1.
    b. (50 баллов) Придумайте эффективный алгоритм, который находит i1, . . . , ik ∈ N, что αi1. . . αik = βi1. . . βik, либо определяет, что их не существует.

© 2014-2019 HwProj