On the weak-prefix search problem