Create an efficient (time and memory wise) for the following:

Create an efficient (time and memory wise) for the following:
You have a dictionary of names of phone numbers. As a user is searching for a name it should show all possible combinations.
For example. As user types 'D' it should show all names beginning with D. And then when user types 'a', it should show all names beginning 'Da' etc. Something like Google sense does. So at each point of time show end users the possible combinations.
Part II. The string could be random in nature and user need not begin at the start. For example, in the name Daniel, the user can give string 'nie' and the algorithm should show all names in the dictionary with substring 'nie' which of course will include 'Daniel' and many others. You have to design a memory and time inexpensive operation.

For the first problem, a prefix tree is the most optimal solution.
For the second problem, a suffix tree might be what you need.