On Suffix Tree Breadth

Article English OPEN
Badkobeh, Golnaz; Karkkainen, Juha; Puglisi, Simon; Zhukova, Bella;
  • Publisher: Springer Verlag

The suffix tree—the compacted trie of all the suffixes of a string—is the most important and widely-used data structure in string processing. We consider a natural combinatorial question about suffix trees: for a string S of length n, how many nodes νS(d)νS(d) can there... View more
  • References (6)

    1. Apostolico, A., Crochemore, M., Farach-Colton, M., Galil, Z., Muthukrishnan, S.: 40 years of su x trees. Commun. ACM 59(4), 66{73 (2016)

    2. Karkkainen, J., Kempa, D., Piatkowski, M.: Tighter bounds for the sum of irreducible LCP values. Theor. Comput. Sci. 656, 265{278 (2016), https://doi.org/ 10.1016/j.tcs.2015.12.009

    3. Karkkainen, J., Manzini, G., Puglisi, S.J.: Permuted longest-common-pre x array. In: Combinatorial Pattern Matching, 20th Annual Symposium, CPM 2009. Lecture Notes in Computer Science, vol. 5577, pp. 181{192. Springer (2009), https://doi. org/10.1007/978-3-642-02441-2_17

    4. Karkkainen, J., Piatkowski, M., Puglisi, S.J.: String inference from longest-commonpre x array. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. pp. 62:1{62:14 (2017), https://doi.org/10.4230/ LIPIcs.ICALP.2017.62

    5. Makinen, V., Belazzougui, D., Cunial, F., Tomescu, A.I.: Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing. Cambridge University Press (2015), http://www.genome-scale.info/

    6. Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory. pp. 1{11. IEEE Computer Society (1973)

  • Related Organizations (1)
  • Metrics
Share - Bookmark