{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T05:08:12Z","timestamp":1761973692311,"version":"build-2065373602"},"publisher-location":"Berlin, Heidelberg","reference-count":68,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642389047"},{"type":"electronic","value":"9783642389054"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38905-4_1","type":"book-chapter","created":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T03:28:54Z","timestamp":1368674934000},"page":"1-10","source":"Crossref","is-referenced-by-count":3,"title":["Forty Years of Text Indexing"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Apostolico","sequence":"first","affiliation":[]},{"given":"Maxime","family":"Crochemore","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Farach-Colton","sequence":"additional","affiliation":[]},{"given":"Zvi","family":"Galil","sequence":"additional","affiliation":[]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: Pattern matching in Z-compressed files. In: Proceedings of the 5th ACM-SIAM Annual Symposium on Discrete Algorithms, Arlington, VA, pp. 705\u2013714 (1994)"},{"issue":"2","key":"1_CR2","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1006\/jcss.1996.0023","volume":"52","author":"A. Amir","year":"1996","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: Pattern matching in Z-compressed files. J. Comput. Syst. Sci.\u00a052(2), 299\u2013307 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR3","series-title":"NATO Advanced Science Institutes, Series F","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-82456-2_6","volume-title":"Combinatorial Algorithms on Words","author":"A. Apostolico","year":"1985","unstructured":"Apostolico, A.: The myriad virtues of suffix trees. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words. NATO Advanced Science Institutes, Series F, vol.\u00a012, pp. 85\u201396. Springer, Berlin (1985)"},{"issue":"3\/4","key":"1_CR4","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1089\/10665270360688020","volume":"10","author":"A. Apostolico","year":"2003","unstructured":"Apostolico, A., Bock, M.E., Lonardi, S.: Monotony of surprise and large-scale quest for unusual words. Journal of Computational Biology\u00a010(3\/4), 283\u2013311 (2003)","journal-title":"Journal of Computational Biology"},{"issue":"3","key":"1_CR5","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.jbiotec.2010.05.006","volume":"149","author":"A. Apostolico","year":"2010","unstructured":"Apostolico, A., Denas, O., Dress, A.: Efficient tools for comparative substring analysis. Journal of Biotechnology\u00a0149(3), 120\u2013126 (2010)","journal-title":"Journal of Biotechnology"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF01762122","volume":"3","author":"A. Apostolico","year":"1988","unstructured":"Apostolico, A., Iliopoulos, C., Landau, G.M., Schieber, B., Vishkin, U.: Parallel construction of a suffix tree with applications. Algorithmica\u00a03, 347\u2013365 (1988)","journal-title":"Algorithmica"},{"issue":"3","key":"1_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(83)90109-3","volume":"22","author":"A. Apostolico","year":"1983","unstructured":"Apostolico, A., Preparata, F.P.: Optimal off-line detection of repetitions in a string. Theor. Comput. Sci.\u00a022(3), 297\u2013315 (1983)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1_CR8","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/BF01955046","volume":"15","author":"A. Apostolico","year":"1996","unstructured":"Apostolico, A., Preparata, F.P.: Data structures and algorithms for the strings statistics problem. Algorithmica\u00a015(5), 481\u2013494 (1996)","journal-title":"Algorithmica"},{"issue":"5","key":"1_CR9","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1137\/S0097539793246707","volume":"26","author":"B.S. Baker","year":"1997","unstructured":"Baker, B.S.: Parameterized duplication in strings: Algorithms and an application to software maintenance. SIAM J. Comput.\u00a026(5), 1343\u20131362 (1997)","journal-title":"SIAM J. Comput."},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/3-540-60922-9_45","volume-title":"STACS 96","author":"M.-P. B\u00e9al","year":"1996","unstructured":"B\u00e9al, M.-P., Mignosi, F., Restivo, A.: Minimal forbidden words and symbolic dynamics. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol.\u00a01046, pp. 555\u2013566. Springer, Heidelberg (1996)"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The ICA problem revisited. In: Gonnet, G.H., Panario, D., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"issue":"1","key":"1_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(85)90157-4","volume":"40","author":"A. Blumer","year":"1985","unstructured":"Blumer, A., Blumer, J., Ehrenfeucht, A., Haussler, D., Chen, M.T., Seiferas, J.: The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci.\u00a040(1), 31\u201355 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR13","first-page":"349","volume-title":"Proceedings of the 16th ACM Symposium on the Theory of Computing","author":"A. Blumer","year":"1984","unstructured":"Blumer, A., Blumer, J., Ehrenfeucht, A., Haussler, D., McConnell, R.: Building a complete inverted file for a set of text files in linear time. In: Proceedings of the 16th ACM Symposium on the Theory of Computing, pp. 349\u2013351. ACM Press, Washington, D.C. (1984)"},{"issue":"3","key":"1_CR14","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A. Blumer","year":"1987","unstructured":"Blumer, A., Blumer, J., Ehrenfeucht, A., Haussler, D., McConnell, R.: Complete inverted files for efficient text retrieval and analysis. J. Assoc. Comput. Mach.\u00a034(3), 578\u2013595 (1987)","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1007\/3-540-45465-9_62","volume-title":"Automata, Languages and Programming","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Lyngs\u00f8, R.B., \u00d6stlin, A., Pedersen, C.N.S.: Solving the string statistics problem in time $\\mathcal{O}(n\\log n)$. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 728\u2013739. Springer, Heidelberg (2002)"},{"key":"1_CR16","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical Report 124, Digital Equipments Corporation (May 1994)"},{"issue":"1","key":"1_CR17","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2012.04.031","volume":"450","author":"S. Chairungsee","year":"2012","unstructured":"Chairungsee, S., Crochemore, M.: Using minimal absent words to build phylogeny. Theoretical Computer Science\u00a0450(1), 109\u2013116 (2012)","journal-title":"Theoretical Computer Science"},{"key":"1_CR18","unstructured":"Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage. In: Proceedings of the 7th ACM-SIAM Annual Symposium on Discrete Algorithms, Atlanta, Georgia, pp. 383\u2013391 (1996)"},{"issue":"1","key":"1_CR19","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0304-3975(86)90041-1","volume":"45","author":"M. Crochemore","year":"1986","unstructured":"Crochemore, M.: Transducers and repetitions. Theor. Comput. Sci.\u00a045(1), 63\u201386 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/3-540-17660-8_45","volume-title":"TAPSOFT 1987 Proceedings of the International Joint Conference on Theory and Practice of Software Development, Pisa, Italy, March 1987.","author":"M. Crochemore","year":"1987","unstructured":"Crochemore, M.: Longest common factor of two words. In: Ehrig, H., Kowalski, R., Levi, G., Montanari, U. (eds.) CAAP 1987 and TAPSOFT 1987. LNCS, vol.\u00a0249, pp. 26\u201336. Springer, Heidelberg (1987)"},{"key":"1_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"M. Crochemore","year":"2007","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press, Cambridge (2007)"},{"issue":"3","key":"1_CR22","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0020-0190(98)00104-5","volume":"67","author":"M. Crochemore","year":"1998","unstructured":"Crochemore, M., Mignosi, F., Restivo, A.: Automata and forbidden words. Information Processing Letters\u00a067(3), 111\u2013117 (1998)","journal-title":"Information Processing Letters"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Mignosi, F., Restivo, A., Salemi, S.: Data compression using antidictonaries. Proceedings of the I.E.E.E.\u00a088(11), 1756\u20131768 (2000); Special issue Lossless data compression, Storer, J. (ed.)","DOI":"10.1109\/5.892711"},{"issue":"1","key":"1_CR24","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0304-3975(91)90073-B","volume":"88","author":"M. Crochemore","year":"1991","unstructured":"Crochemore, M., Rytter, W.: Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays. Theor. Comput. Sci.\u00a088(1), 59\u201382 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR25","unstructured":"Crochemore, M., Rytter, W.: Text algorithms. Oxford University Press (1994)"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: Proceedings of the 38th IEEE Annual Symposium on Foundations of Computer Science, Miami Beach, FL, pp. 137\u2013143 (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"8","key":"1_CR27","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1016\/j.ic.2008.12.010","volume":"207","author":"P. Ferragina","year":"2009","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G.: The myriad virtues of wavelet trees. Inf. Comput.\u00a0207(8), 849\u2013866 (2009)","journal-title":"Inf. Comput."},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. J. ACM\u00a057(1) (2009)","DOI":"10.1145\/1613676.1613680"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: FOCS, pp. 390\u2013398 (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"issue":"4","key":"1_CR30","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"1_CR31","first-page":"240","volume-title":"Proceedings of the 16th ACM Symposium on the Theory of Computing","author":"Z. Galil","year":"1984","unstructured":"Galil, Z.: Optimal parallel algorithms for string matching. In: Proceedings of the 16th ACM Symposium on the Theory of Computing, pp. 240\u2013248. ACM Press, Washington, D.C. (1984)"},{"issue":"1-3","key":"1_CR32","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/S0019-9958(85)80031-0","volume":"67","author":"Z. Galil","year":"1985","unstructured":"Galil, Z.: Optimal parallel algorithms for string matching. Inf. Control\u00a067(1-3), 144\u2013157 (1985)","journal-title":"Inf. Control"},{"key":"1_CR33","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: SODA, pp. 841\u2013850 (2003)"},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In: Proceedings of the ACM Symposium on the Theory of Computing, Portland, Oregon, pp. 397\u2013406. ACM Press (2000)","DOI":"10.1145\/335305.335351"},{"key":"1_CR35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees and sequences: computer science and computational biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"1_CR36","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.jcss.2004.03.004","volume":"69","author":"D. Gusfield","year":"2004","unstructured":"Gusfield, D., Stoye, J.: Linear time algorithms for finding and representing all the tandem repeats in a string. J. Comput. Syst. Sci.\u00a069(4), 525\u2013546 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1_CR37","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"key":"1_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/3-540-56024-6_19","volume-title":"Combinatorial Pattern Matching","author":"L.C.K. Hui","year":"1992","unstructured":"Hui, L.C.K.: Color set size problem with applications to string matching. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) CPM 1992. LNCS, vol.\u00a0644, pp. 230\u2013243. Springer, Heidelberg (1992)"},{"key":"1_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/3-540-45061-0_73","volume-title":"Automata, Languages and Programming","author":"J. K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work suffix array construction. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 943\u2013955. Springer, Heidelberg (2003)"},{"key":"1_CR40","first-page":"125","volume-title":"Proceedings of the 4th ACM Symposium on the Theory of Computing","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M., Miller, R.E., Rosenberg, A.L.: Rapid identification of repeated patterns in strings, trees and arrays. In: Proceedings of the 4th ACM Symposium on the Theory of Computing, pp. 125\u2013136. ACM Press, Denver, CO (1972)"},{"key":"1_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T. Kasai","year":"2001","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 181\u2013192. Springer, Heidelberg (2001)"},{"issue":"4","key":"1_CR42","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF00292114","volume":"24","author":"M. Kempf","year":"1987","unstructured":"Kempf, M., Bayer, R., G\u00fcntzer, U.: Time optimal left to right construction of position trees. Acta. Inform.\u00a024(4), 461\u2013474 (1987)","journal-title":"Acta. Inform."},{"issue":"2-4","key":"1_CR43","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.jda.2004.08.019","volume":"3","author":"D.K. Kim","year":"2005","unstructured":"Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing suffix arrays in linear time. J. Discrete Algorithms\u00a03(2-4), 126\u2013142 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"2-4","key":"1_CR44","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.jda.2004.08.002","volume":"3","author":"P. Ko","year":"2005","unstructured":"Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. J. Discrete Algorithms\u00a03(2-4), 143\u2013156 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"1_CR45","first-page":"1","volume":"1","author":"A.N. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Problems of Information Transmission\u00a01(1), 1\u20137 (1965)","journal-title":"Problems of Information Transmission"},{"issue":"13","key":"1_CR46","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1002\/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O","volume":"29","author":"S. Kurtz","year":"1999","unstructured":"Kurtz, S.: Reducing the space requirements of suffix trees. Softw. Pract. Exp.\u00a029(13), 1149\u20131171 (1999)","journal-title":"Softw. Pract. Exp."},{"key":"1_CR47","unstructured":"Landau, G.M.: String matching in erroneus input. Ph. D. Thesis, Department of Computer Science, Tel-Aviv University (1986)"},{"key":"1_CR48","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A. Lempel","year":"1976","unstructured":"Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Trans. Inf. Theory\u00a022, 75\u201381 (1976)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"1_CR49","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1137\/0209061","volume":"9","author":"M.E. Majster","year":"1980","unstructured":"Majster, M.E., Ryser, A.: Efficient on-line construction and correction of position trees. SIAM J. Comput.\u00a09(4), 785\u2013807 (1980)","journal-title":"SIAM J. Comput."},{"key":"1_CR50","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. In: Proceedings of the 1st ACM-SIAM Annual Symposium on Discrete Algorithms, San Francisco, CA, pp. 319\u2013327 (1990)"},{"issue":"5","key":"1_CR51","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput.\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1_CR52","first-page":"262","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. Algorithms\u00a023(2), 262\u2013272 (1976)","journal-title":"J. Algorithms"},{"key":"1_CR53","unstructured":"Muthukrishnan, S.: Efficient algorithms for document listing problems. In: Proceedings of the 13th ACM-SIAM Annual Symposium on Discrete Algorithms, pp. 657\u2013666 (2002)"},{"key":"1_CR54","doi-asserted-by":"crossref","unstructured":"Na, J.C., Ferragina, P., Giancarlo, R., Park, K.: Two-dimensional pattern indexing. In: Encyclopedia of Algorithms (2008)","DOI":"10.1007\/978-0-387-30162-4_442"},{"issue":"2","key":"1_CR55","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s00453-007-0063-x","volume":"48","author":"J.C. Na","year":"2007","unstructured":"Na, J.C., Giancarlo, R., Park, K.: On-line construction of two-dimensional suffix trees in o(n2 log n) time. Algorithmica\u00a048(2), 173\u2013186 (2007)","journal-title":"Algorithmica"},{"key":"1_CR56","unstructured":"Poe, E.A.: The Gold-Bug and Other Tales. Dover Thrift Editions Series. Dover (1991)"},{"key":"1_CR57","unstructured":"Pratt, V.: Improvements and applications for the Weiner repetition finder, Manuscript (1975)"},{"issue":"1","key":"1_CR58","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/322234.322237","volume":"28","author":"M. Rodeh","year":"1991","unstructured":"Rodeh, M., Pratt, V., Even, S.: Linear algorithm for data compression via string matching. J. Assoc. Comput. Mach.\u00a028(1), 16\u201324 (1991)","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR59","first-page":"392","volume":"21","author":"A.O. Slisenko","year":"1980","unstructured":"Slisenko, A.O.: Determination in real time of all the periodicities in a word. Sov. Math. Dokl.\u00a021, 392\u2013395 (1980)","journal-title":"Sov. Math. Dokl."},{"key":"1_CR60","doi-asserted-by":"publisher","first-page":"1316","DOI":"10.1007\/BF01084395","volume":"22","author":"A.O. Slisenko","year":"1983","unstructured":"Slisenko, A.O.: Detection of periodicities and string matching in real time. J. Sov. Math.\u00a022, 1316\u20131386 (1983)","journal-title":"J. Sov. Math."},{"key":"1_CR61","unstructured":"Storer, J.A.: NP-completeness results concerning data compression. Report 234, Princeton University (1977)"},{"key":"1_CR62","doi-asserted-by":"crossref","unstructured":"Storer, J.A., Szymanski, T.G.: The macro model for data compression. In: Proceedings of the 10th ACM Symposium on the Theory of Computing, San Diego, CA, pp. 30\u201339. ACM Press (1978)","DOI":"10.1145\/800133.804329"},{"issue":"4","key":"1_CR63","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"J.A. Storer","year":"1982","unstructured":"Storer, J.A., Szymanski, T.G.: Data compression via textual substitution. J. Assoc. Comput. Mach.\u00a029(4), 928\u2013951 (1982)","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR64","first-page":"1","volume":"1","author":"A. Thue","year":"1912","unstructured":"Thue, A.: \u00dcber die gegenseitige lage gleicher teile gewisser zeichenreichen. Nor. Vidensk. Selsk. Skr. Mat. Nat. Kl.\u00a01, 1\u201367 (1912)","journal-title":"Nor. Vidensk. Selsk. Skr. Mat. Nat. Kl."},{"issue":"3","key":"1_CR65","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica\u00a014(3), 249\u2013260 (1995)","journal-title":"Algorithmica"},{"issue":"2","key":"1_CR66","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1089\/cmb.2006.13.336","volume":"13","author":"I. Ulitsky","year":"2006","unstructured":"Ulitsky, I., Burstein, D., Tuller, T., Chor, B.: The average common substring approach to phylogenomic reconstruction. Journal of Computational Biology\u00a013(2), 336\u2013350 (2006)","journal-title":"Journal of Computational Biology"},{"key":"1_CR67","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1006\/jmbi.1998.1947","volume":"281","author":"J. van Helden","year":"1998","unstructured":"van Helden, J., Andr\u00e9, B., Collado-Vides, J.: Extracting regulatory sites from the upstream region of the yeast genes by computational analysis of oligonucleotides. J. Mol. Biol.\u00a0281, 827\u2013842 (1998)","journal-title":"J. Mol. Biol."},{"key":"1_CR68","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory, Washington, DC, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38905-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T10:18:43Z","timestamp":1746008323000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-38905-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642389047","9783642389054"],"references-count":68,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38905-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}