title: Which C# data structure allows searching a pair of strings most efficiently for substrings?
body: <p>I have a data structure which consists of pairs of values, the first of which is an integer and the second of which is an alphanumeric string (which may begin with digits):</p>
  
  <pre><code>+--------+-----------------+
  | Number | Name            |
  +--------+-----------------+
  | 15     | APPLES          |
  | 16     | APPLE COMPUTER  |
  | 17     | ORANGE          |
  | 21     | TWENTY-1        |
  | 291    | 156TH ELEMENT   |
  +--------+-----------------+
  </code></pre>
  
  <p>A table of these would comprise up to 100,000 rows. </p>
  
  <p>I'd like to provide a lookup function in which the user can look up either the number (as if it were a string), or pieces of the string. Ideally the lookup will be "live" as the user types; after each keystroke (or maybe after a brief delay ~250-500 ms) a new search will be done to find the most likely candidates. So, for example searching on</p>
  
  <ul>
  <li><code>1</code> will return <code>15  APPLES</code>, <code>16  APPLE COMPUTER</code>, <code>17  ORANGE</code>, and
  <code>291  156TH ELEMENT</code></li>
  <li><code>15</code> will narrow the search to <code>15  APPLES</code>, <code>291  156TH ELEMENT</code></li>
  <li><code>AP</code> will return <code>15  APPLES</code> and <code>16  APPLE COMPUTER</code></li>
  <li>(ideally, but not required) <code>ELEM</code> will return <code>291  156TH ELEMENT</code>.</li>
  </ul>
  
  <p>I was thinking about using two <code>Dictionary&lt;string, string&gt;</code>s since ultimately the <code>int</code>s are being compared as <code>string</code>s -- one will index by the integer part and the other by the string part. </p>
  
  <p>But really searching by substring shouldn't use a hash function, and it seems wasteful to use twice the memory that I feel like I should need.</p>
  
  <p>Ultimately the question is, is there any well-performing way to text search two large lists simultaneously for substrings?</p>
  
  <p>Failing that, how about a <code>SortedDictionary</code>? Might increase performance but still wouldn't solve the hash problem.</p>
  
  <p>Thought about creating a regex on the fly, but I would think that would perform terribly.</p>
  
  <p>I'm new to C# (having come from the Java world) so I haven't looked into LINQ yet; is that the answer? </p>
  
  <p><strong>EDIT 18:21 EST</strong>: None of the strings in the "Name" field will be longer than 12-15 characters, if that affects your potential solution.</p>