[raincom]

Why can't one construct a prefix tree of all prefixes, then start process from the right to left (assume that it is an offline algorithm)?

[j-pb]

Because you can walk search trees from their root but not from their leafs.