title: Finding all matches from a large set of Strings in a smaller String
body: <p>I have a large set of Words and Phrases (a lexicon or dictionary) which includes wildcards. I need to find all instances of those Words and Phrases within a much smaller String (~150 characters at the moment). </p>
  
  <p>Initially, I wanted to run the operation in reverse; that is to check to see if each word in my smaller string exists within the Lexicon, which could be implemented as a Hash Table. The problem is that some of these values in my Lexicon are not single words and many are wildcards (e.g. substri*).</p>
  
  <p>I'm thinking of using the <a href="http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm" rel="nofollow">Rabin-Karp algorithm</a> but I'm not sure this is the best choice.</p>
  
  <p><strong>What's an efficient algorithm or method to perform this operation?</strong></p>
  
  <p><em>Sample Data</em>:</p>
  
  <p>The dictionary contains <em>hundreds of words</em> and can potentially expand. These words may end with wildcard characters (asterisks). Here are some random examples:</p>
  
  <ul>
  <li>good</li>
  <li>bad</li>
  <li>freed*</li>
  <li>careless*</li>
  <li>great loss</li>
  </ul>
  
  <p>The text we are analyzing (at this point) are short, informal (grammar-wise) English statements. The prime example of text (again, at this point in time) would be a Twitter Tweet. These are limited to roughly 140 Characters. For example:</p>
  
  <pre><code>Just got the Google nexus without a contract. Hands down its the best phone 
  I've ever had and the only thing that could've followed my N900.
  </code></pre>
  
  <p>While it may be helpful to note that we are performing very simple Sentiment Analysis on this text; our Sentiment Analysis technique is <em>not</em> my concern. I'm simply migrating an existing solution to a "real-time" processing system and need to perform some optimizations.</p>