Создать индекс для поиска подстроки?

Я хочу выполнить общий поиск подстроки среди миллиардов строк. Требование немного отличается от обычного полнотекстового поиска, потому что я хочу, чтобы запрос «ubst» также мог попасть в «substr».

Способны ли Lucene или Sphinx сделать это? Если нет, как вы думаете, как это лучше всего сделать?