Алфавит {a, b, c, 1, ., +, ∗}. Даны α - регулярое выражение, буква x и натуральное число k. Вывести длину кратчайшего слова из языка L, содержащего суффикс x^k.

1. Читаем из строки посимвольно.

Если есть буква, то создаем автомат с единственным переходом по этой букве и кладем на стек. Если встречаем символы . или +, то достаем из стека два последних автомата и приненяем к ним операцию, возврашающую автомат.

Операция . соединяет два автомата переходом по эпсилон.

Операция + создаем новую стартовую вершину, из которой идут переходы по епсилон к двум автоматам и из их предыдущих терминальных вершин делаем переходы по епсилон к новой терминальной вершине.

Если встречаем символ * тогда к последнему автомату добавляем новую начальную вершину из которой будет переход по епсилон к старой стартовой вершине и по епсилон переход в новую конечную вершину, из которой могу также попасть в начальную.

2. Когда получили автомат, запускаем поиск вершин, из которых начинается наш суффикс. Если не нашли такие вершины, то выводим "INF", что означает отсутствие решения.

3. Находим минимальное расстояние от начальной вершины, до тех вершин, откуда начинается суффикс.

4. Прибавляем к этому минимальному расстонию длину нашего суффикса.

5. Есть также возможность вывести картинку построенного автомата.

Для того, чтобы запустить программу, воспользуйтесь:

./build.sh

Для того, чтобы открыть картинку автомата, воспользуйтесь флагом:

-DDUMP

Для того, чтобы запустить тесты, воспользуйтесь флагом:

-DTEST_BUILD