Simply use BEGINSWITH instead of CONTAINS.
Edit
If you need to search in every word of a string, there is a technique which was presented in one of the talks in WWDC 2010. The basic idea is to create a separate entity Word which contains a single word and a reference of the containing object (the entity you’re searching). You then do the search on the Word entity and return the objects which are related to the found words.
The query would then look something like this (provided you have a many-to-one relationship between your entity and Word: “ANY words BEGINSWITH[c] %@”
This would mean that you have to setup the words when creating your objects though.