the first thing that comes to mind for me may be alot of work.

i would start with something like a binary search tree, hopefully balanced (so red-black tree or avl tree - the only balanced trees i have studied). then maybe just work through the string letter by letter, matching letters as you go along with letters in the tree. i would think if you had a good algorithm, this could speed things up... maybe.

just my thoughts, throwing them out there for you.