Searching a new string - adding a string to the set - would require comparing against all items in the set, yes. That's a much less daunting prospect than what you said:
You really have to scan your complete dataset on every search.Building the index, or adding to it, is not fast (without some heuristics applied) but searching using the index isn't bad.
