Какая структура данных C # позволяет наиболее эффективно искать подстроки в паре строк?

У меня есть структура данных, которая состоит из пар значений, первое из которых является целым числом, а второе - буквенно-цифровой строкой (которая может начинаться с цифр):

+--------+-----------------+
| Number | Name            |
+--------+-----------------+
| 15     | APPLES          |
| 16     | APPLE COMPUTER  |
| 17     | ORANGE          |
| 21     | TWENTY-1        |
| 291    | 156TH ELEMENT   |
+--------+-----------------+

Их таблица может содержать до 100 000 строк.

Я хотел бы предоставить функцию поиска, в которой пользователь может искать либо число (как если бы это была строка), либо фрагменты строки. В идеале поиск будет «живым» по мере ввода пользователем; после каждого нажатия клавиши (или, может быть, после небольшой задержки ~ 250-500 мс) будет выполняться новый поиск, чтобы найти наиболее вероятных кандидатов.Так, например, поиск по

• 1 вернет 15 ЯБЛОК , 16 ЯБЛОЧНЫЙ КОМПЬЮТЕР , 17 ОРАНЖЕВЫЙ и 291 156-Й ЭЛЕМЕНТ
• 15 сузит поиск до 15 ЯБЛОК , 291 156-Й ЭЛЕМЕНТ
• AP вернет 15 ЯБЛОК и 16 APPLE COMPUTER
• (в идеале, но не обязательно) ELEM вернет 291 156TH ELEMENT .

Я думал об использовании двух Dictionary s, так как в конечном итоге int s сравниваются как string s - один будет индексировать целой частью, а другой - строковой.

Но на самом деле поиск по подстроке не должен использовать хеш-функцию, и кажется расточительным использовать вдвое больше памяти, чем я считаю нужным.

В конечном счете, вопрос в том, есть ли какой-либо эффективный способ текстового поиска в двух больших списках одновременно для подстрок?

В противном случае, как насчет SortedDictionary ? Может повысить производительность, но все же не решит проблему с хешем.

Подумал о создании регулярного выражения "на лету", но я думаю, что это ужасно сработает.

Я новичок в C # (пришедший из мира Java), поэтому я еще не изучал LINQ; это ответ?

РЕДАКТИРОВАТЬ 18:21 EST : Ни одна из строк в поле «Имя» не будет длиннее 12-15 символов, если это повлияет на ваше потенциальное решение.