Do you always receive all the strings all at once, or do you need to add to the existing set?

If you need to add them, would a linked list help?

Once you have your sorted list, you could use a binary search; ie,
1. start at the middle string
2. see if your target is before or after this string
3. repeat from 1, using the appropriate half of the list