The data structure itself should sort of "build itself" if you create an FST with increasing integers because the "shared suffix" should be pushed towards the root anyway, so the only thing would be to correct values on all outgoing arcs (they need to contain the count of leaves on the subtree).... but then, this may be tricky if arc values are vcoded... I'd have to think how to do this.

There are actually two things:

a) performance; you need to descend in the automaton and some bookkeeping to maintain the count of nodes; this adds overhead,

b) size; the procedure for storing/ calculating perfect hashes I described requires leaf counts on each arc and these are usually large integers. Even vcoded they bloat the resulting data structure.

Dawid