{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T16:02:11Z","timestamp":1770480131918,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540403111","type":"print"},{"value":"9783540448884","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44888-8_5","type":"book-chapter","created":{"date-parts":[[2007,3,5]],"date-time":"2007-03-05T11:34:12Z","timestamp":1173094452000},"page":"55-69","source":"Crossref","is-referenced-by-count":43,"title":["Fast Lightweight Suffix Array Construction and Checking"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Burkhardt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,5,27]]},"reference":[{"key":"5_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/3-540-45784-4_35","volume-title":"Proc. 2nd Workshop on Algorithms in Bioinformatics","author":"M. I. Abouelhoda","year":"2002","unstructured":"M. I. Abouelhoda, S. Kurtz, and E. Ohlebusch. The enhanced suffix array and its applications to genome analysis. In Proc. 2nd Workshop on Algorithms in Bioinformatics, volume 2452 of LNCS, pages 449\u2013463. Springer, 2002."},{"issue":"3","key":"5_CR2","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/PL00009260","volume":"23","author":"A. Andersson","year":"1999","unstructured":"A. Andersson, N. J. Larsson, and K. Swanson. Suffix trees on words. Algorithmica, 23(3):246\u2013260, 1999.","journal-title":"Algorithmica"},{"key":"5_CR3","unstructured":"J. L. Bentley and R. Sedgewick. Fast algorithms for sorting and searching strings. In Proc. 8th Annual Symposium on Discrete Algorithms, pages 360\u2013369. ACM, 1997."},{"issue":"1","key":"5_CR4","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1145\/200836.200880","volume":"42","author":"M. Blum","year":"1995","unstructured":"M. Blum and S. Kannan. Designing programs that check their work. J. ACM, 42(1):269\u2013291, Jan. 1995.","journal-title":"J. ACM"},{"key":"5_CR5","unstructured":"M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm. Technical Report 124, SRC (digital, Palo Alto), May 1994."},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"R. Clifford. Distributed and paged suffix trees for large genetic databases. In Proc. 14th Annual Symposium on Combinatorial Pattern Matching. Springer, 2003. This volume.","DOI":"10.1007\/3-540-44888-8_6"},{"issue":"1\u20132","key":"5_CR7","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0020-0190(00)00080-6","volume":"75","author":"C. J. Colbourn","year":"2000","unstructured":"C. J. Colbourn and A. C. H. Ling. Quorums from difference covers. Inf. Process. Lett., 75(1\u20132):9\u201312, July 2000.","journal-title":"Inf. Process. Lett."},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"M. Farach. Optimal suffix tree construction with large alphabets. In Proc. 38th Annual Symposium on Foundations of Computer Science, pages 137\u2013143. IEEE, 1997.","DOI":"10.1109\/SFCS.1997.646102"},{"key":"5_CR9","unstructured":"G. Gonnet, R. Baeza-Yates, and T. Snider. New indices for text: PAT trees and PAT arrays. In W. B. Frakes and R. Baeza-Yates, editors, Information Retrieval: Data Structures & Algorithms. Prentice-Hall, 1992."},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"H. Itoh and H. Tanaka. An efficient method for in memory construction of suffix arrays. In Proc. 6th Symposium on String Processing and Information Retrieval, pages 125\u2013136. IEEE, 1999.","DOI":"10.1109\/SPIRE.1999.796581"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"J. K\u00e4rkk\u00e4inen and P. Sanders. Simple linear work suffix array construction. In Proc. 13th International Conference on Automata, Languages and Programming. Springer, 2003. To appear.","DOI":"10.1007\/3-540-45061-0_73"},{"key":"5_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/3-540-61332-3_155","volume-title":"Proc. 2nd Annual International Conference on Computing and Combinatorics","author":"J. K\u00e4rkk\u00e4inen","year":"1996","unstructured":"J. K\u00e4rkk\u00e4inen and E. Ukkonen. Sparse suffix trees. In Proc. 2nd Annual International Conference on Computing and Combinatorics, volume 1090 of LNCS, pages 219\u2013230. Springer, 1996."},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"R. M. Karp, R. E. Miller, and A. L. Rosenberg. Rapid identification of repeated patterns in strings, trees and arrays. In Proc. 4th Annual Symposium on Theory of Computing, pages 125\u2013136. ACM, 1972.","DOI":"10.1145\/800152.804905"},{"key":"5_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Proc. 12th Annual Symposium on Combinatorial Pattern Matching","author":"T. Kasai","year":"2001","unstructured":"T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park. Linear-time longest-common-prefix computation in suffix arrays and its applications. In Proc. 12th Annual Symposium on Combinatorial Pattern Matching, volume 2089 of LNCS, pages 181\u2013192. Springer, 2001."},{"issue":"11","key":"5_CR15","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1109\/12.61044","volume":"39","author":"J. Kilian","year":"1990","unstructured":"J. Kilian, S. Kipnis, and C. E. Leiserson. The organization of permutation architectures with bused interconnections. IEEE Transactions on Computers, 39(11):1346\u20131358, Nov. 1990.","journal-title":"IEEE Transactions on Computers"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. In Proc. 14th Annual Symposium on Combinatorial Pattern Matching. Springer, 2003. This volume.","DOI":"10.1007\/3-540-44888-8_14"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"P. Ko and S. Aluru. Linear time construction of suffix arrays. In Proc. 14th Annual Symposium on Combinatorial Pattern Matching. Springer, 2003. This volume.","DOI":"10.1007\/3-540-44888-8_15"},{"issue":"13","key":"5_CR18","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":"S. Kurtz. Reducing the space requirement of suffix trees. Software \u2014 Practice and Experience, 29(13):1149\u20131171, 1999.","journal-title":"Software \u2014 Practice and Experience"},{"key":"5_CR19","series-title":"Technical report LU-CSTR","volume-title":"Faster suffix sorting","author":"N. J. Larsson","year":"1999","unstructured":"N. J. Larsson and K. Sadakane. Faster suffix sorting. Technical report LU-CSTR: 99-214, Dept. of Computer Science, Lund University, Sweden, 1999."},{"key":"5_CR20","unstructured":"W.-S. Luk and T.-T. Wong. Two new quorum based algorithms for distributed mutual exclusion. In Proc. 17th International Conference on Distributed Computing Systems, pages 100\u2013106. IEEE, 1997."},{"issue":"5","key":"5_CR21","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"U. Manber and G. Myers. Suffix arrays: A new method for on-line string searches. SIAM J. Comput., 22(5):935\u2013948, Oct. 1993.","journal-title":"SIAM J. Comput."},{"key":"5_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1007\/3-540-45749-6_61","volume-title":"Proc. 10th Annual European Symposium on Algorithms","author":"G. Manzini","year":"2002","unstructured":"G. Manzini and P. Ferragina. Engineering a lightweight suffix array construction algorithm. In Proc. 10th Annual European Symposium on Algorithms, volume 2461 of LNCS, pages 698\u2013710. Springer, 2002."},{"issue":"2","key":"5_CR23","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E. M. McCreight","year":"1976","unstructured":"E. M. McCreight. A space-economic suffix tree construction algorithm. J. ACM, 23(2):262\u2013272, 1976.","journal-title":"J. ACM"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"J. Seward. On the performance of BWT sorting algorithms. In Proc. Data Compression Conference, pages 173\u2013182. IEEE, 2000.","DOI":"10.1109\/DCC.2000.838157"},{"key":"5_CR25","unstructured":"J. Seward. The bzip2 and libbzip2 official home page, 2002. http:\/\/sources.redhat.com\/bzip2\/ ."},{"issue":"3","key":"5_CR26","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249\u2013260, 1995.","journal-title":"Algorithmica"},{"issue":"6","key":"5_CR27","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1145\/268999.269003","volume":"44","author":"H. Wasserman","year":"1997","unstructured":"H. Wasserman and M. Blum. Software reliability via run-time result-checking. J. ACM, 44(6):826\u2013849, Nov. 1997.","journal-title":"J. ACM"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"P. Weiner. Linear pattern matching algorithm. In Proc. 14th Symposium on Switching and Automata Theory, pages 1\u201311. IEEE, 1973.","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44888-8_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T01:41:31Z","timestamp":1556156491000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44888-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540403111","9783540448884"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-44888-8_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}