I want to do general substring search among billions of strings. The requirement is a little different from general fulltext search because I want a query "ubst" also can hit "substr".
Is Lucene or Sphinx capable of doing this? If not, what's the best way do you think to do this?