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