best way to search - alternatives to full text (thinking sphinx)?

Currently I am using thinking_sphinx, but to my dismay, a lot of hosts
do not have sphinx installed and are unwilling to install it "because
of security reasons". This leaves me with a very limited option of
hosting as I'd have to get a VPS/dedicated but I just don't have that
kind of money, so I'll have to stick to shared.

Long story short, is there a good alternative to full text searching?
The only solution I am aware of right now is using searchlogic, but
since it uses LIKE so I would have to change back to full text after a
while.

Currently I am using thinking_sphinx, but to my dismay, a lot of hosts
do not have sphinx installed and are unwilling to install it "because
of security reasons".

Sounds like a lame excuse to me...

This leaves me with a very limited option of
hosting as I'd have to get a VPS/dedicated but I just don't have that
kind of money, so I'll have to stick to shared.

SliceHost has a $20/mo option. If you're site isn't super big that would probably be enough...

Long story short, is there a good alternative to full text searching?

MySQL has full text built in if you set up the tables a certain way. PostgreSQL has tsearch2, but unlikely your ISP will configure that if they won't configure sphinx.

I've recently been using Heroku. I'm not aware of how well they do for
large apps, but for low-budget stuff, they're awesome!