Algorythm.txt

для решения задачи решим подзадачу: найти максимальный префикс слова, также являющийся префиксом какого-то слова из языка задаваемого регулярным выражением
для этого построим детерменированный автомат, и найдем все "нетупиковые" состояния. Нетупиковыми назовем те, оказавгись в которых можно добраться до терминальной. Для этого построим граф на состояних, проведя ребро i -> j, если есть буква c, такая что есть переход из j в i по букве c. Далее запустим dfs от каждой терминальной вершины в полученом графе, заходя в каждую вершину не более одного раза, тогда из тех и только тех вершин, где побывал этот dfs можно попасть в какую-то терминальную. То есть только они - нетупиковые. Теперь будем идти с данным словом по автомату, пока назодимс в нетупиковых, если попали в тупиковую - то максимальный префикс закончился, поскольку из этой вершины нельзя попасть в терминальную, а пока мы находимся в нетупиковых, то есть "путь" до терминальной, то есть есть слово из данного автомата, с таким префиксом.

далее заметим, что максимальный искомый суффикс - перевернутый максимальный перфикс для развернутого слова и "перевернутого" регулярного выражения, где под перевернутым регулярным выражением имеется ввиду регулярное выражение, принимающее все те и только те слова, перевернутые которые принимает изначальное регулярное выражение.

чтобы "развернуть" регулярное выражение, построим по нему дерево построения, tree(".ab") - дерево состоящее из вершины со знаком "." и с двумя ребрами - в tree("a") и tree("b"), для  "+ab" аналогично, для "*a" - тоже, но только ребро одно,  а tree("c") где c - буква - вершина с буквой c

тогда несложно по дереву восстановить regex
regex(tree(".ab")) = "." + tree("a") + tree("b")   
regex(tree("+ab")) = "+" + tree("a") + tree("b")
regex(tree("*a")) = "*" + tree("a")   
regex(tree("c")) = "c" где с - буква

а так же несложно восстановить "перевернутоe" r_regex()
r_regex(tree(".ab")) = "." + tree("b") + tree("a")        
r_regex(tree("+ab")) = "+" + tree("a") + tree("b") или же "+" + tree("b") + tree("a") так как для regex сложение коммутативно
r_regex(tree("*a")) = "*" + tree("a")
r_regex(tree("c")) = "c" где с - буква    

так же такое дерево можно использовать для смены нотации