(17 вариант)
На ввод подается язык из символов из {a, b, c, ., +, *} и слово состоящее из {a, b, c}. Программа выдает длину самого длинного суффикса слова, являющегося также суффиксом некоторого слова из языка.
Считаем язык и, с помощью стека, построим недетерминированный конечный автомат для него и инвертируем (за O(len(L)) L - регулярное выражение для языка). Мы построили автомат для обратного к нашему языку. Далее считаем слово и развернем его. Теперь осталось найти длину максимального префикса слова, которое подходит в наш автомат. Будем делать это поиском в глубину с запоминанием ответа для вершины (за O(len(P) * len(L)) P - паттерн). Общая асимптотика - O(len(P) * len(L)).
Для того чтобы запустить тесты, воспользуйтесь командами:
cmake -DDEBUG=1
make
./first-practical-work
Для запуска программы воспользуйтесь командами:
cmake
make
./first-practical-work