On the weak prefix-search problem