У меня есть потенциально бесконечный набор символов: A, B, C, ... Существует также особый специальный символ-заполнитель ? (его смысл будет объяснен ниже).
Рассмотрим непустые конечные деревья такие, что каждый node имеет прикрепленный к нему символ и 0 или более непустых поддеревьев. Порядок поддеревьев данного node значителен (так, например, если есть node с двумя поддеревами, мы можем различить, какой из них оставлен, а какой правильный). Любой заданный символ может появляться в дереве 0 больше времени, прикрепленного к различным узлам. Символ-заполнитель ? может быть прикреплен только к листовым узлам (т.е. Узлам, не имеющим поддеревьев). Из обычного определения дерева следует, что деревья ацикличны.
Требование о конечности означает, что общее число узлов в дереве является положительным конечным целым числом. Из этого следует, что общее количество прикрепленных символов, глубина дерева и общее количество узлов в каждом поддереве все конечны.
Деревья задаются в функциональной нотации: a node представляется прикрепленным к нему символом, и, если есть какие-либо поддеревья, за ним следуют круглые скобки, содержащие разделенные запятыми списки поддеревьев, представленные рекурсивно в так же. Итак, например дерево
A
/ \
? B
/ \
A C
/|\
A C Q
\
?
представляется как A(?,B(A(A,C,Q(?)),C)).
У меня есть предварительно вычисленный неизменный набор деревьев S, который будет использоваться в качестве шаблонов для соответствия. Обычно набор имеет деревья ~ 10 5 и каждый его элемент обычно будет иметь ~ 10-30 узлов. Я могу использовать много времени, чтобы заранее создать любое представление S, которое наилучшим образом соответствует моей проблеме, указанной ниже.
Мне нужно написать функцию, которая принимает дерево T (обычно с узлами ~ 10 2) и проверяет как можно быстрее, если T содержит в качестве поддерева любой элемент S, при условии, что любой node с символом-заполнителем ? соответствует любому непустому поддереву (оба, когда он отображается в T или в элементе S).
Пожалуйста, предложите структуру данных для хранения набора S и алгоритма проверки соответствия. Любой язык программирования или псевдокод в порядке.
