{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:36:12Z","timestamp":1725795372941},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319079585"},{"type":"electronic","value":"9783319079592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07959-2_35","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T12:44:25Z","timestamp":1402404265000},"page":"412-423","source":"Crossref","is-referenced-by-count":29,"title":["LCP Array Construction in External Memory"],"prefix":"10.1007","author":[{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"first","affiliation":[]},{"given":"Dominik","family":"Kempa","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"35_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"M.I. Abouelhoda","year":"2004","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms\u00a02(1), 53\u201386 (2004)","journal-title":"J. Discrete Algorithms"},{"key":"35_CR2","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.jda.2012.07.007","volume":"18","author":"T. Beller","year":"2013","unstructured":"Beller, T., Gog, S., Ohlebusch, E., Schnattinger, T.: Computing the longest common prefix array based on the Burrows-Wheeler transform. J. Discrete Algorithms\u00a018, 22\u201331 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"Bingmann, T., Fischer, J., Osipov, V.: Inducing suffix and lcp arrays in external memory. In: Proc. ALENEX 2013, pp. 88\u2013102. SIAM (2013)","DOI":"10.1137\/1.9781611972931.8"},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"Dementiev, R., K\u00e4rkk\u00e4inen, J., Mehnert, J., Sanders, P.: Better external memory suffix array construction. ACM J. Experimental Algorithmics\u00a012 (2008)","DOI":"10.1145\/1227161.1402296"},{"issue":"6","key":"35_CR5","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1002\/spe.844","volume":"38","author":"R. Dementiev","year":"2008","unstructured":"Dementiev, R., Kettner, L., Sanders, P.: STXXL: standard template library for XXL data sets. Softw., Pract. Exper.\u00a038(6), 589\u2013637 (2008)","journal-title":"Softw., Pract. Exper."},{"issue":"3","key":"35_CR6","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/s00453-011-9535-0","volume":"63","author":"P. Ferragina","year":"2012","unstructured":"Ferragina, P., Gagie, T., Manzini, G.: Lightweight data indexing and compression in external memory. Algorithmica\u00a063(3), 707\u2013730 (2012)","journal-title":"Algorithmica"},{"key":"35_CR7","doi-asserted-by":"crossref","unstructured":"Gog, S., Ohlebusch, E.: Fast and lightweight lcp-array construction algorithms. In: Proc. ALENEX 2011, pp. 25\u201334. SIAM (2011)","DOI":"10.1137\/1.9781611972917.3"},{"key":"35_CR8","unstructured":"Gonnet, G.H., Baeza-Yates, R.A., Snider, T.: New indices for text: Pat trees and Pat arrays. In: Frakes, W.B., Baeza-Yates, R. (eds.) Information Retrieval: Data Structures & Algorithms, pp. 66\u201382. Prentice\u2013Hall (1992)"},{"key":"35_CR9","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D.: Engineering a lightweight external memory suffix array construction algorithm. In: Proc. ICABD 2014, pp. 53\u201360 (2014)"},{"key":"35_CR10","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Lempel-Ziv parsing in external memory. In: Proc. DCC 2014, pp. 153\u2013162. IEEE CS (2014)","DOI":"10.1109\/DCC.2014.78"},{"key":"35_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-642-02441-2_17","volume-title":"Combinatorial Pattern Matching","author":"J. K\u00e4rkk\u00e4inen","year":"2009","unstructured":"K\u00e4rkk\u00e4inen, J., Manzini, G., Puglisi, S.J.: Permuted longest-common-prefix array. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009 Lille. LNCS, vol.\u00a05577, pp. 181\u2013192. Springer, Heidelberg (2009)"},{"key":"35_CR12","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)"},{"issue":"6","key":"35_CR13","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J. K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM\u00a053(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"key":"35_CR14","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":"1-2","key":"35_CR15","first-page":"191","volume":"56","author":"V. M\u00e4kinen","year":"2003","unstructured":"M\u00e4kinen, V.: Compact suffix array \u2014 a space efficient full-text index. Fundamenta Informaticae\u00a056(1-2), 191\u2013210 (2003)","journal-title":"Fundamenta Informaticae"},{"issue":"5","key":"35_CR16","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, G.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comp.\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comp."},{"key":"35_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/978-3-540-27810-8_32","volume-title":"Algorithm Theory - SWAT 2004","author":"G. Manzini","year":"2004","unstructured":"Manzini, G.: Two space saving tricks for linear time lcp array computation. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 372\u2013383. Springer, Heidelberg (2004)"},{"key":"35_CR18","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys\u00a039(1), article 2 (2007)","DOI":"10.1145\/1216370.1216372"},{"issue":"10","key":"35_CR19","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1109\/TC.2010.188","volume":"60","author":"G. Nong","year":"2011","unstructured":"Nong, G., Zhang, S., Chan, W.H.: Two efficient algorithms for linear time suffix array construction. IEEE Trans. Computers\u00a060(10), 1471\u20131484 (2011)","journal-title":"IEEE Trans. Computers"},{"key":"35_CR20","unstructured":"Ohlebusch, E.: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag (2013)"},{"issue":"2","key":"35_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1242471.1242472","volume":"39","author":"S.J. Puglisi","year":"2007","unstructured":"Puglisi, S.J., Smyth, W.F., Turpin, A.: A taxonomy of suffix array construction algorithms. ACM Computing Surveys\u00a039(2), 1\u201331 (2007)","journal-title":"ACM Computing Surveys"},{"key":"35_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-540-92182-0_14","volume-title":"Algorithms and Computation","author":"S.J. Puglisi","year":"2008","unstructured":"Puglisi, S.J., Turpin, A.: Space-time tradeoffs for Longest-Common-Prefix array computation. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 124\u2013135. Springer, Heidelberg (2008)"},{"issue":"4","key":"35_CR23","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1561\/0400000014","volume":"2","author":"J.S. Vitter","year":"2006","unstructured":"Vitter, J.S.: Algorithms and data structures for external memory. Foundations and Trends in Theoretical Computer Science\u00a02(4), 305\u2013474 (2006)","journal-title":"Foundations and Trends in Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07959-2_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T21:51:00Z","timestamp":1558907460000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07959-2_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319079585","9783319079592"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07959-2_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}