{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:27:28Z","timestamp":1761611248945},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642037832"},{"type":"electronic","value":"9783642037849"}],"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-03784-9_9","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T14:47:42Z","timestamp":1250866062000},"page":"90-101","source":"Crossref","is-referenced-by-count":44,"title":["A Linear-Time Burrows-Wheeler Transform Using Induced Sorting"],"prefix":"10.1007","author":[{"given":"Daisuke","family":"Okanohara","sequence":"first","affiliation":[]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical report, Digital Equipment Corporation (1994)"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal Suffix Tree Construction with Large Alphabets. In: Proc. of FOCS, pp. 137\u2013143 (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"4","key":"9_CR3","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1145\/1082036.1082043","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Compression boosting in optimal linear time. Journal of the ACM\u00a052(4), 688\u2013713 (2005)","journal-title":"Journal of the ACM"},{"issue":"2","key":"9_CR4","first-page":"378","volume":"35","author":"R. Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arryas and suffix trees with applications to text indexing and string matching. Computing\u00a035(2), 378\u2013407 (2005)","journal-title":"Computing"},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s00453-006-1228-8","volume":"48","author":"W.-K. Hon","year":"2007","unstructured":"Hon, W.-K., Lam, T.-W., Sadakane, K., Sung, W.-K., Yiu, S.-M.: A space and time efficient algorithm for constructing compressed suffix arrays. Algorithmica\u00a048(1), 23\u201336 (2007)","journal-title":"Algorithmica"},{"issue":"6","key":"9_CR6","doi-asserted-by":"publisher","first-page":"2162","DOI":"10.1137\/070685373","volume":"38","author":"W.K. Hon","year":"2009","unstructured":"Hon, W.K., Sadakane, K., Sung, W.K.: Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. SIAM Journal on Computing\u00a038(6), 2162\u20132178 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"9_CR7","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(3), 249\u2013257 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"9_CR8","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. ACM\u00a053(6), 918\u2013936 (2006)","journal-title":"ACM"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-44888-8_14","volume-title":"Combinatorial Pattern Matching","author":"D.-K. Kim","year":"2003","unstructured":"Kim, D.-K., Sim, J.S., Park, H.-J., Park, K.: Linear-time construction of suffix arrays. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 186\u2013199. Springer, Heidelberg (2003)"},{"key":"9_CR10","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.W.: Space-efficient linear time construction of suffix arrays. Discrete Algorithm\u00a03, 143\u2013156 (2005)","journal-title":"Discrete Algorithm"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Lippert, R.: Space-efficient whole genome comparisons with burrows-wheeler transforms. j. of computational biology. Computational Biology\u00a012(4) (2005)","DOI":"10.1089\/cmb.2005.12.407"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Lippert, R., Mobarry, C., Walenz, B.: A space-efficient construction of the burrows wheeler transform for genomic data. In: Computational Biology (2005)","DOI":"10.1089\/cmb.2005.12.943"},{"issue":"1-3","key":"9_CR13","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.tcs.2007.05.030","volume":"385","author":"J. Chae Na","year":"2007","unstructured":"Chae Na, J., Park, K.: Alphabet-independent linear-time construction of compressed suffix arrays using o(nlogn)-bit working space. Theoretical Computer Science\u00a0385(1-3), 127\u2013136 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"9_CR14","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G. Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys\u00a039(1), 2\u201361 (2007)","journal-title":"ACM Computing Surveys"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Nong, G., Zhang, S., Chan, W.H.: Linear suffix array construction by almost pure induced-sorting. In: Proc. of DCC (2009)","DOI":"10.1109\/DCC.2009.42"},{"key":"9_CR16","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. of SODA, pp. 233\u2013242 (2002)"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03784-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T03:42:37Z","timestamp":1558496557000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03784-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642037832","9783642037849"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03784-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}