Comment by Y_Y

Depending on what you understand by the term "prefix" you can dramatically shrink the search space without doing any thinking.