{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T20:50:59Z","timestamp":1769719859824,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642024405","type":"print"},{"value":"9783642024412","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02441-2_17","type":"book-chapter","created":{"date-parts":[[2009,6,17]],"date-time":"2009-06-17T13:19:32Z","timestamp":1245244772000},"page":"181-192","source":"Crossref","is-referenced-by-count":84,"title":["Permuted Longest-Common-Prefix Array"],"prefix":"10.1007","author":[{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_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. Journal of Discrete Algorithms\u00a02, 53\u201386 (2004)","journal-title":"Journal of Discrete Algorithms"},{"key":"17_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1227161.1402296","volume":"12","author":"R. Dementiev","year":"2008","unstructured":"Dementiev, R., K\u00e4rkk\u00e4inen, J., Mehnert, J., Sanders, P.: Better external memory suffix array construction. ACM Journal of Experimental Algorithmics\u00a012, 1\u201324 (2008)","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The String B-Tree: A new data structure for string search in external memory and its applications. Journal of the ACM\u00a046, 236\u2013280 (1999)","journal-title":"Journal of the ACM"},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-540-69068-9_16","volume-title":"Combinatorial Pattern Matching","author":"J. Fischer","year":"2008","unstructured":"Fischer, J., M\u00e4kinen, V., Navarro, G.: An(other) entropy-bounded compressed suffix tree. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 152\u2013165. Springer, Heidelberg (2008)"},{"key":"17_CR5","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)"},{"key":"17_CR6","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.tcs.2007.07.018","volume":"387","author":"J. K\u00e4rkk\u00e4inen","year":"2007","unstructured":"K\u00e4rkk\u00e4inen, J.: Fast BWT in small space by blockwise suffix sorting. Theoretical Computer Science\u00a0387, 249\u2013257 (2007)","journal-title":"Theoretical Computer Science"},{"key":"17_CR7","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":"17_CR8","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)"},{"key":"17_CR9","unstructured":"Kelbert, A.: Memorial website of Dima Khmelev (2006), \n                  \n                    http:\/\/mgg.coas.oregonstate.edu\/~anya\/dima\/index-eng.html"},{"key":"17_CR10","unstructured":"Khmelev, D.: Personal communication (2004)"},{"key":"17_CR11","unstructured":"Khmelev, D.: Program lcp version 0.1.9 (2004), \n                  \n                    http:\/\/www.math.toronto.edu\/dkhmelev\/PROGS\/misc\/lcp-eng.html"},{"key":"17_CR12","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, 191\u2013210 (2003); Special Issue - Computing Patterns in Strings","journal-title":"Fundamenta Informaticae"},{"key":"17_CR13","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 Journal on Computing\u00a022, 935\u2013948 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"17_CR14","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 computation. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 372\u2013383. Springer, Heidelberg (2004)"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys 39 (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"17_CR16","volume-title":"Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX 2007)","author":"D. Okanohara","year":"2007","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX 2007). SIAM, Philadelphia (2007)"},{"key":"17_CR17","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, 1\u201331 (2007)","journal-title":"ACM Computing Surveys"},{"key":"17_CR18","series-title":"LNCS","first-page":"124","volume-title":"ISAAC 2008","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)"},{"key":"17_CR19","unstructured":"Sadakane, K.: Succinct representations of lcp information and improvements in the compressed suffix arrays. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 225\u2013232. ACM\/SIAM (2002)"},{"key":"17_CR20","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K. Sadakane","year":"2003","unstructured":"Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. Journal of Algorithms\u00a048, 294\u2013313 (2003)","journal-title":"Journal of Algorithms"},{"key":"17_CR21","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1145\/1376616.1376683","volume-title":"Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data","author":"R. Sinha","year":"2008","unstructured":"Sinha, R., Puglisi, S.J., Moffat, A., Turpin, A.: Improving suffix array locality for fast pattern matching on disk. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 661\u2013672. ACM Press, New York (2008)"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the 14th annual Symposium on Foundations of Computer Science, pp. 1\u201311 (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\/978-3-642-02441-2_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T12:50:56Z","timestamp":1548420656000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02441-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642024405","9783642024412"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02441-2_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}