Задачи с семинара 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\)). Оцените число вершин и рёбер в сжатом боре.