Time optimal left to right construction of position trees (Q1092659)

The authors present a new algorithm for the on-line construction of position trees. The position tree for a given text is a trie index spelling out for every position the shortest substring starting at that position and occurring nowhere else in the text. This auxiliary text representation structure yields an efficient solution for multiple pattern matching. Hence efficient construction (and correction) algorithms of position trees have become an interesting subject of research. The new position tree construction method is developed starting from a general construction scheme by stepwise refinements. Infix trees are a useful theoretical concept to describe the progress of the construction and to prove the correctness of the algorithm. An additional threading within the trees connecting every node with its ``tail node'' is the key idea which enables us to read an input string from left to right and thereby to generate its position tree within the best possible time (proportional to the number of tree nodes). Changes in the text obviously require the correction of its position tree. Efficient updating methods also including the strength of tail nodes will be the subject of a forthcoming study by the first author.