On-line construction of position heaps

Blumer, 1985, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 31, 10.1016/0304-3975(85)90157-4 Clark, 1996, Efficient suffix trees on secondary storage (extended abstract), 383 Coffman, 1970, File structures using hash functions, Communications of the ACM, 13, 427, 10.1145/362686.362693 Cormen, 1999 Crochemore, 1986, Transducers and repetitions, Theoretical Computer Science, 45, 63, 10.1016/0304-3975(86)90041-1 Crochemore, 1988, String matching with constraints, vol. 324, 44 Crochemore, 1994 Ehrenfeucht, 2011, Position heaps: A simple and dynamic text indexing data structure, Journal of Discrete Algorithms, 9, 100, 10.1016/j.jda.2010.12.001 Farach, 1997, Optimal suffix tree construction with large alphabets, 137 Fredkin, 1960, Trie memory, Communications of the ACM, 3, 490, 10.1145/367390.367400 Gusfield, 1997 Jacobson, 1989, Space-efficient static trees and graphs, 549 Munro, 2001, Succinct representation of balanced parentheses and static trees, SIAM J. Comput., 31, 762, 10.1137/S0097539799364092 Y. Nakashima, T. I, S. Inenaga, H. Bannai, M. Takeda, The position heap of a trie, in: Proc. of the 19th Symposium on String Processing and Information Retrieval (SPIREʼ12), Cartagena, Colombia, October 21–25, 2012, in: Lecture Notes in Computer Science, Springer-Verlag, 2012, in press. Navarro, 2007, Compressed full-text indexes, ACM Comput. Surv., 39, 10.1145/1216370.1216372 Stanley, 1999, Enumerative Combinatorics, vol. 1 Ukkonen, 1995, On-line construction of suffix-trees, Algorithmica, 14, 249, 10.1007/BF01206331 P. Weiner, Linear pattern matching algorithm, in: 14th Annual IEEE Symposium on Switching and Automata Theory, 1973, pp. 1–11.