Several nontrivial applications of subword trees have been developed since their first appearance. Some such applications depart considerably from the original motivations. A brief account of them is attempted here. Subword trees fit in the general subject of digital search indexes [KN]. In fact their earliest conception is somewhat implicit in Morrison's 'PATRICIA' tries [MO]. Several linear time and space subword tree constructions are available today [MC, PR, SL] (see also [AH]), following the pioneering work by Weiner (WE]. More compact alternate versions have been introduced recently in [BL, BE, CS2]. The data structures developed in this endeavor are variously referred to as B-trees, position trees, suffix (or prefix) trees, subword trees, repetition finders, directed acyclic word graphs, etc. A concise account of the similarities and discrepancies among the various approaches is presented in [SEt, Cst]. On line (though not linear tim~) constructions are discussed in [MR]. In this paper, we choose to refer mostly to t~e version in [MC], to which we also conform as much as possible as for basic definitions and notations. However, the properties presented here are to a large extent independent of the particular incarnation of a subword tree, and, from the conceptual standpoint, so are indeed the associated criteria and constructions. This paper addresses itself to a reader with scarce previous exposure to the subject, but it does assume some familiarity with elementary facts and concepts in combinatorics on words. The paper is also self-contained in the description of the various applications presented. However, some proofs are only sketched; the reader is also pointed to the referenced literature when it comes to constructions too elaborate to be given here in full details. Finally, the list given here is not meant to be exhaustive. In particular, it reflects some recent involvements of this author, and his personal perspective. The paper is organized as follows. Basic properties and applications of subword trees are outlined in the next section. In Section 2, such trees are treated as a unifying framework for the description of a class of linear time sequential data compression techniques that is becoming increasingly popular. In Section 3, we take steps from one such data compression paradigm and use subword trees to decide whether a word contains a square subword, in linear time. We show next how subword trees can be used also to spot all such squares, as well as to establish bounds on the number of cube subwords in a string. Augmented subword trees are suited to allocate the statistics without overlap of all subwords of a textstring, as highlighted in Section 4. In Section 5, we mention two applications in which subword trees are outperformed by other approaches.
Suffix trees are extremely important for a large number of string processing problems REF .