Постановка задачи

Дано регулярное выражение a и слово v. Требуется найти наибольший префикс слова v, лежащий в языке, задаваемым регулярным выражением a.

Реализуем следующий алгоритм

1. Построим автомат, распознающий язык a
2. Запустим обход автомата. Попытаемся увеличить наибольший префикс.

Построение автомата:

Так как регулярное выражение дано в постфиксном виде, будем строить автомат по индукции.

1. Движемся по регулярному выражению:
	a. Если текущий символ буква <- Строим автомат, в котором ребро ведет из корня в лист по текущему символу. Считаем Лист терминальной вершиной. Закидываем текущий автомат в стек.
	b. Если текущий символ знак операции, то в зависимости от сигнатуры операции достаем либо один, либо два автомата из стека и применяем к ним текущую операцию.

Реализация операций:

Операция "*" <- Closer:

​ Достроим ребро, ведующее по пустому слову из всех терминалов в корень. Добавим корень в терминалы.

Операция "." <- Mul (first, second):

​ Из всех терминалов первого автомата достраиваем ребро по пустому слову в корень второго автомата. Результирующее множество терминальных вершин состоит только из терминалов второго автомата. Не коммутативно!

Операция "+" <- Add (first, second):

​ Из корня первого автомата достраиваем ребро по пустому слову в корень второго автомата. Результирующее множество терминальных вершин состоит из всех терминалов первого и второго автоматов.

Проблема:

​ Можем зациклиться при обходе. (Переходим в ту же самую вершину по пустому слову)

Решение:

​ Добавим проверку -> Если мы перешли в корень и текущий рассматриваемый символ - нулевой символ строки, то все пошло по кругу. Значит, завершаем текущий рекурсивный вызов.