title: Search for strings matching the pattern "abc:*:xyz" in less than O(n)
body: <p>Given a bunch of strings I need to find those which match 3 kinds of patterns:</p>
  
  <ul>
  <li>Prefix search - abc*</li>
  <li>Glob-like pattern - abc:*:xyz</li>
  <li>Suffix search - *xyz</li>
  </ul>
  
  <p>where * is a wildcard (and can match any number of chars).</p>
  
  <p>Now the straight-forward solution is just to scan every string and see if it matches the target pattern. But this is O(n). If I stored the strings in a balanced search tree, I can do the prefix queries in O(log n). If I created one more tree with all the strings essentially reversed, I can do the the suffix queries in O(log n). Is there a clever way to search for the "abc:*:xyz" patterns efficiently?</p>