Home practicum number one.
Task:
№ 8: Given α, letter x and natural number k. Output the length of the shortest word in language L, containing prefix x^k.
I solved task with C++
Implementation details:
- Регулярное выражение может быть любой строкой в алфавите {a, b, c, 1, ., +, ∗}.
- В случае, если ответ является целым числом, то я вывожу это число.
- В случае, если такого числа не существует, то INF.
- В случае, если входная строка не является корректным регулярным выражением в обратной польской записи, вывожу ERROR.
Первым компонентом входа является регулярное выражение α в обратной польской записи, задающее язык L.
- В случае, если Вы хотите запустить программу на своих тестах, то нужно поменять в CMakeLists.txt аргумент tests.cpp на main.cpp. В таком случае, входные данные получаются из stdin и выводятся в stdout.
- Программа компилируется/запускается с последеней стабильной версией GCC.
- Код удовлетворяет разумным требованиям к стилю написания и вычислительной эффективности (но используется throw, чтобы выпрыгнуть из большой вложенности функций в случае ошибки). Не используются библиотеки для работы с регулярными выражениями и конечными автоматами.
- Код программы размещён в виде приватного репозитория на GitHub с открытым доступом для аккаунта mizabrik. Помимо файлов с решением задачи, в репозитории присутствует README-файл с описанием алгоритма и оценкой сложности его работы, а также набор тестов (tests.txt), проверяющие корректность работы алгоритма.
- Есть CMakeLists.txt с целью на запуск тестов и, если нужно, сборку программы.
- Можно запустить программу в режиме DEBUG, передав ей соответствующий аргумент в параметрах компилятора при компиляции или написав "#define DEBUG" в начале файла solution.cpp.
- Работа алгоритма заключается в последовательной обработке символов регулярного выражения α в обратной польской записи. При этом используется динамическое программирование и стек, чтобы хранить состояния.
- В состоянии есть массив, для i-ого элемента которого я храню минимальное значение = (длины слова - i), для слова, у которого префикс x^i и которое можно вывести из текущей обработанной регулярки. (То есть я храню длину остатка минимального слова без префикса.) Если ничего не выводится, то в соответствующем элементу хранится большая константа.
- На символы {a, b, c, 1} создается новое состояние, которое кладется на стек, этот процесс выполняется за O(k), потому что нужно установить все значения массива.
- На символ "+"" также тратится O(k), потому что можно пройтись по массиву нового состояния и установить в его i-ый элемент минимум из i-ых элементов массивов 2 взятых со стека состояний.
- На символы {., ∗} тратится уже O(k^2), потому что там используется динамика: для i-ого состояния я проверяю j-ое и i-j-ое у двух состояний, взятых со стека.
Можно не расписывать все случаи перебора в {., ∗}, потому что их несложно осознать при чтении кода. Так или иначе, основную суть алгоритма я расписал выше.
- Соотвественно на каждый символ в худшем случае тратится O(k^2). Поэтому итоговая ассимптотика = O(|α| * k^2).