nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

A Suffix Tree Or Not a Suffix Tree?

verfasst von : Tatiana Starikovskaya, Hjalte Wedel Vildhøj

Erschienen in: Combinatorial Algorithms

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we study the structure of suffix trees. Given an unlabeled tree $\tau $ on n nodes and suffix links of its internal nodes, we ask the question “Is $\tau $ a suffix tree?", i.e., is there a string S whose suffix tree has the same topological structure as $\tau $? We place no restrictions on S, in particular we do not require that S ends with a unique symbol. This corresponds to considering the more general definition of implicit or extended suffix trees. Such general suffix trees have many applications and are for example needed to allow efficient updates when suffix trees are built online. We prove that $\tau $ is a suffix tree if and only if it is realized by a string S of length $n-1$, and we give a linear-time algorithm for inferring S when the first letter on each edge is known. This generalizes the work of I et al. [Discrete Appl. Math. 163, 2014].

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Metric Dimension for Amalgamations of Graphs

Nächstes Kapitel Deterministic Algorithms for the Independent Feedback Vertex Set Problem

In the literature the standard terminology is suffix trees for $-suffix trees and extended/implicit suffix trees [3, 12] for suffix trees of strings not ending with $.

Apostolico, A., Crochemore, M., Farach-Colton, M., Galil, Z., Muthukrishnan, S.: Forty years of text indexing. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 1–10. Springer, Heidelberg (2013) CrossRef

Bannai, H., Inenaga, S., Shinohara, A., Takeda, M.: Inferring strings from graphs and arrays. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 208–217. Springer, Heidelberg (2003) CrossRef

Breslauer, D., Hariharan, R.: Optimal parallel construction of minimal suffix and factor automata. Parallel Process. Lett. 06(01), 35–44 (1996)MathSciNetCrossRef

Breslauer, D., Italiano, G.F.: On suffix extensions in suffix trees. Theor. Comp. Sci. 457, 27–34 (2012)MATHMathSciNetCrossRef

Cazaux, B., Rivals, E.: Reverse engineering of compact suffix trees and links: a novel algorithm. J. Discrete Algorithms 28, 9–22 (2014)MATHMathSciNetCrossRef

Clément, J., Crochemore, M., Rindone, G.: Reverse engineering prefix tables. In: Proceedings of the 26th STACS, pp. 289–300 (2009)

Crochemore, M., Iliopoulos, C.S., Pissis, S.P., Tischler, G.: Cover array string reconstruction. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 251–259. Springer, Heidelberg (2010) CrossRef

Duval, J.P., Lecroq, T., Lefebvre, A.: Border array on bounded alphabet. J. Autom. Lang. Comb. 10(1), 51–60 (2005)MATHMathSciNet

Duval, J.P., Lecroq, T., Lefebvre, A.: Efficient validation and construction of border arrays and validation of string matching automata. RAIRO Theor. Inform. Appl. 43, 281–297 (2009)MATHMathSciNetCrossRef

10.

Duval, J.P., Lefebvre, A.: Words over an ordered alphabet and suffix permutations. RAIRO Theor. Inform. Appl. 36(3), 249–259 (2002)MATHMathSciNetCrossRef

11.

Gawrychowski, P., Jeż, A., Jeż, Ł.: Validating the Knuth-Morris-Pratt failure function, fast and online. Theory Comput. Syst. 54(2), 337–372 (2014)CrossRef

12.

Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York (1997) MATHCrossRef

13.

I, T., Inenaga, S., Bannai, H., Takeda, M.: Verifying and enumerating parameterized border arrays. Theor. Comput. Sci. 412(50), 6959–6981 (2011)MATHMathSciNetCrossRef

14.

I, T., Inenaga, S., Bannai, H., Takeda, M.: Counting parameterized border arrays for a binary alphabet. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 422–433. Springer, Heidelberg (2009) CrossRef

15.

I., Tomohiro, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki: Verifying a Parameterized Border Array in O(n $^\text{1.5 }$) Time. In: Amir, Amihood, Parida, Laxmi (eds.) CPM 2010. LNCS, vol. 6129, pp. 238–250. Springer, Heidelberg (2010) CrossRef

16.

I, T., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from suffix trees and links on a binary alphabet. Discrete Appl. Math. 163, 316–325 (2014)MathSciNetCrossRef

17.

Kucherov, G., Tóthmérész, L., Vialette, S.: On the combinatorics of suffix arrays. Inf. Process. Lett. 113(22–24), 915–920 (2013)MATHCrossRef

18.

Lu, W., Ryan, P.J., Smyth, W.F., Sun, Y., Yang, L.: Verifying a border array in linear time. J. Comb. Math. Comb. Comput. 42, 223–236 (2002)MATHMathSciNetCrossRef

19.

Starikovskaya, T., Vildhøj, H.W.: A suffix tree or not a suffix tree. arXiv (2014). http://arxiv.org/abs/1403.1364

20.

Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249–260 (1995)MATHMathSciNetCrossRef

21.

Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the 14th FOCS (SWAT), pp. 1–11 (1973)

Titel: A Suffix Tree Or Not a Suffix Tree?
verfasst von: Tatiana Starikovskaya
Hjalte Wedel Vildhøj
Verlag: Springer International Publishing
Buch: Combinatorial Algorithms
Print ISBN: 978-3-319-19314-4

Electronic ISBN: 978-3-319-19315-1

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-19315-1_30

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"