title: How to match a tree against a large set of patterns?
body: <p>I have a potentially infinite set of symbols: <code>A, B, C, ...</code> There is also a distinct special placeholder symbol <code>?</code> (its meaning will be explained below).</p>
  
  <p>Consider non-empty finite trees such that every node has a symbol attached to it and 0 or more non-empty sub-trees. The order of sub-trees of a given node is significant (so, for example, if there is a node with 2 sub-trees, we can distinguish which one is left and which one is right). Any given symbol can appear in the tree 0 of more times attached to different nodes. The placeholder symbol <code>?</code> can be attached only to leaf nodes (i.e. nodes having no sub-trees). It follows from the usual definition of a tree that trees are acyclic.</p>
  
  <p>The finiteness requirement means that the total number of nodes in a tree is a positive finite integer. It follows that the total number of attached symbols, the tree depth and the total number of nodes in every sub-tree are all finite.</p>
  
  <p>Trees are given in a functional notation: a node is represented by a symbol attached to it and, if there are any sub-trees, it is followed by parentheses containing comma-separated list of sub-trees represented recursively in the same way. So, for example the tree</p>
  
  <pre><code>                    A
                     / \
                    ?   B
                       / \
                      A   C
                     /|\
                    A C Q
                         \
                          ?
  </code></pre>
  
  <p>is represented as <code>A(?,B(A(A,C,Q(?)),C))</code>.</p>
  
  <p>I have a pre-calculated unchanging set of trees <strong>S</strong> that will be used as patterns to match. The set will typically have ~ 10<sup>5</sup> trees, and every its element will typically have ~ 10-30 nodes. I can use a plenty of time to create beforehand any representation of <strong>S</strong> that will best suit my problem stated below.</p>
  
  <p>I need to write a function that accepts a tree <strong>T</strong> (typically with ~ 10<sup>2</sup> nodes) and checks as fast as possible if <strong>T</strong> contains as a subtree any element of <strong>S</strong>, provided that any node with placeholder symbol <code>?</code> matches any non-empty subtree (both when it appears in <strong>T</strong> or in an element of <strong>S</strong>).</p>
  
  <p>Please suggest a data structure to store the set <strong>S</strong> and an algorithm to check for a match. Any programing language or a pseudo-code is OK.</p>