City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Семинар 2. Алгоритим Ахо-Корасик
Advanced chapters of algorithms, part 2

What: Seminar
When: Tuesday, 15 February 2022, 00:00–01:30
Where: Онлайн, занятие в zoom

Description

Задачи с семинара 2

Во всех задачах полагаем размер алфавита \(\Sigma\) константным и различаем алфавит \(\Sigma\) и знак суммирования \(\sum\) по размеру.

  1. Дан набор строк \(\left\{s_i\right\}_{i\in\{1,2,\ldots,n\}}\). Постройте за время \(\mathcal O\bigl(n+\sum\limits_{i=1}^n\mathop{\mathrm{len}}s_i\bigr)\) конечный автомат, принимающий только строки, содержащие хотя бы одну из \(s_i\) как подстроку.

  2. Дан набор строк \(\left\{s_i\right\}_{i\in\{1,2,\ldots,n\}}\). Постройте за время \(\mathcal O\bigl(n+\sum\limits_{i=1}^n\mathop{\mathrm{len}}s_i\bigr)\) конечный автомат, принимающий только строки, не содержащие ни одной из строк \(s_i\) как подстроку.

  3. Дан набор строк \(\left\{s_i\right\}_{i\in\{1,2,\ldots,n\}}\). Проверьте за время \(\mathcal O\bigl(n+\sum\limits_{i=1}^n\mathop{\mathrm{len}}s_i\bigr)\), существует ли бесконечная строка, не содержащая ни одной из строк \(s_i\) как подстроку.

  4. Дан набор строк \(\left\{s_i\right\}_{i\in\{1,2,\ldots,n\}}\) и \(\ell\in\mathbb N_0\). Проверьте за время \(\mathcal O\bigl(n+\sum\limits_{i=1}^n\mathop{\mathrm{len}}s_i\bigr)\), существует ли строка длины \(\ell\), не содержащая ни одной из строк \(s_i\) как подстроку.

  5. Дан набор строк \(\left\{s_i\right\}_{i\in\{1,2,\ldots,n\}}\), построим для него сжатый бор, который можно получить из обычного бора стягиванием нетерминальных вершин, имеющих ровно одного родителя и ровно одного ребёнка (в результате таких операций сжатия на рёбрах могут быть написаны не только символы, но и непустые строки, но из каждой вершины для каждого символа \(c\in\Sigma\) выходит не более одной стрелки, помеченной строкой, начинающейся с символа \(c\)). Оцените число вершин и рёбер в сжатом боре.

Video