I don't know any better ways.

You could include a drop down next to the search box so they can specify a Exact, Starts With, Ends With, or Contains search.

This would be a more complex procedure, but executions would speed up more if a user selects Exact or Starts With. I would default the drop down to Exact so most times the user will select that.

I don't know, I am just talking to talk right now...lol.