Note, that it is important to search not only beginnings of items. Treat each word as a possible match.
Exceptional case for endings
In some specific cases, like surnames, it may also be smart to allow searching the endings of words. Names and complex words tend to have memorable suffixes users may want to search by.
((^|\s)input.*)|(.*input($|\s))
Nicely ordered - as all things should be
The last important lesson is the order of results shown to the user.
If you don’t store any tracking of which items are clicked most by users, in which case you would order by such tracking index, we must blindly assume all results are of equal importance.
First list items in which first word was a hit, then items for which second word was a hit, and so on. In some cases, it may also be a good idea to sort the final results alphabetically by the reminder of the word hit.
If you are matching word endings as well, be sure to display them at the end of results. Even though sometimes useful, these are significantly less important than matching word beginnings.