Hacker News Reader

I have a very noob question. For most databases, suffix search is always super slow. However, can't someone just build an index based on the string reversed, then treat suffix search exactly the same way as prefix search? This doubles your index storage requirement. But index storage is generally not a problem. Finally this could be perhaps extended to cover any wildcard searches (hell*world)

View on HN

The issue there is that you're still anchoring your index to one end of the string which means you're not solving the general problem, only a specific manifestation of it.

A general example would be given the string "foo bar baz", your solution could find "foo%" or "%baz" efficiently, but not "%bar%". Its not out of the question if what you really want is a suffix search, but the general problem of finding an internal substring is still less than optimal.

Edit: Formatting

Yep. That is exactly how you solve this problem. I've done this with Lucene and then searched either the regular field or the reversed field depending on the wildcard query.

Reply on news.ycombinator.com