There are two possibilities related to your "search" (partial or exact) and you do not specify which you're using.
Let us imagine the plaintext is ATTACK AT DAWN. Let us suppose that the encryption translates this to QWWQTHXQWXBQNO: each letter is encoded as a different letter regardless of its position (so, A is always encrypted as Q and so on). However obtained, this is a Caesar cipher and is weak. But it allows you to simply search for DAWN because it will always be BQNO.
A different cipher scheme (for example the Vernam cipher) would encode each letter as a different letter depending on its position. So to be sure to find DAWN inside a 1000-character string, you would need to look for 997 different strings - DAWN encoded starting at 0, 1, 2,... 996. This is more secure, and even completely secure if you encode one string. If you encode lots of different records, then this devolves into a Vigenère cipher, which can be attacked. The more the records, the easier the attack.
AES would encode each letter into a different letter depending on its position and what the other letters are. This makes it impossible to look for DAWN because you would need to look for a jillion possible sequences (the encrypted version of DAWN in ATTACK AT DAWN would be be different from the DAWN of RETIRE AT DAWN, even if the word starts at the tenth position in each case).
So, use of a strong cipher means you cannot do partial matches but only full matches.
You can very slightly ameliorate this situation by encoding different, shorter chunks and only looking for matches wider than twice a single chunk. With chunks of 2 characters [only an example, AES won't (efficiently) do that], AW will always be encoded as, say, QR. If you look for DAWN, the plaintext string, once divided in 2-char chunks, will either contain ?D AW N? or DA WN. So you look for DA, AW and WN; if you find the encrypted form of AW, either you retrieve the record, decrypt, and do a plaintext search for confirmation, or you need to also look for additional 625 combinations (from AD AW NA to ZD AW NZ). With bytes, that's actually 65025 combinations. And that's with 2-byte chunks; with N byte chunks you'll need (N-1)^2 combinations, which quickly becomes prohibitive.
And, of course, using short chunks over many records weakens the encryption. In general, the ability of using (arbitrarily small) matches leaks information.
different approach #1
You can perhaps filter the records, without breaking the encryption, and restrict the returned records to a reasonable number. Then, have them transmitted in the encrypted form, and decrypted on the client, and searched again for the string. This allows you zero-trusting the server; the plaintext never exists in the server in any form. You could use a stronger encryption on the records, since you're not going to seach the encrypted returned records and you have to decrypt them all anyway.
different approach #2
With some databases (e.g. MySQL), you can have memory storage transient tablespace, or RAM disks, where the information can be stored in plaintext form.
You can decrypt all the information upon user login and store it in a RAM disk or tablespace, thereby rendering it searchable.
When the system is powered off or brought to rest, that information is lost, unless specific physical attacks are carried out (so-called "cold boot" or "cryo" attacks, involving the rapid refrigeration of RAM chips to preserve their content).
This leaves you vulnerable to the host system being subverted, but if the client's code is sent by the host system (as it usually happens in Web applications), a host subversion will be enough to break the encryption by simply accessing the user's credentials on the client side.
You do have, therefore, to (limitedly) "trust" the server, albeit not at rest.
If the server is just data storage, and the client code is not hosted there, then you can't go this way without implicitly adding trust in the server security.
