Time optimal left to right construction of position trees

Summary In the following paper we are presenting a new algorithm for the on-line construction of position trees. Reading a given input string from left to right we are generating its position tree with the aid of the general concept of infix trees. An additional chain structure within the trees, called tail node connection, enables us to construct the tree within the best possible time (proportional to the number of nodes).