Thanks for the suggestions!
My requirements can be relaxed to full text search, but the problem I had with that approach is I have strings in Chinese, and postgres doesn't seem to support it. Calling to_tsvector() on Chinese characters always returns an empty vector.
A separate table will definitely work, but I was hoping for something more straightforward. I'll use that approach if necessary though.