{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T17:08:44Z","timestamp":1761844124104,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642245824"},{"type":"electronic","value":"9783642245831"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-24583-1_26","type":"book-chapter","created":{"date-parts":[[2011,9,30]],"date-time":"2011-09-30T13:08:23Z","timestamp":1317388103000},"page":"267-277","source":"Crossref","is-referenced-by-count":6,"title":["Compressed Text Indexing with Wildcards"],"prefix":"10.1007","author":[{"given":"Wing-Kai","family":"Hon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsung-Han","family":"Ku","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-642-13509-5_9","volume-title":"Combinatorial Pattern Matching","author":"D. Belazzougui","year":"2010","unstructured":"Belazzougui, D.: Succinct Dictionary Matching with No Slowdown. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 88\u2013100. Springer, Heidelberg (2010)"},{"key":"26_CR2","unstructured":"Burrows, M., Wheeler, D.J.: A Block-sorting Lossless Data Compression Algorithm. Technical Report 124, Digital Equipment Corporation, Paolo Alto, CA, USA (1994)"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"Chien, Y.F., Hon, W.K., Shah, R., Vitter, J.S.: Geometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing. In: DCC, pp. 252\u2013261 (2008)","DOI":"10.1109\/DCC.2008.67"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary Matching and Indexing with Errors and Don\u2019t Cares. In: STOC, pp. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"issue":"4","key":"26_CR5","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. Journal of the ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"Journal of the ACM"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed Representations of Sequences and Full-Text Indexes. ACM Transactions on Algorithms\u00a03(2) (2007)","DOI":"10.1145\/1240233.1240243"},{"issue":"1","key":"26_CR7","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"372","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A Simple Storage Scheme for Strings Achieving Entropy Bounds. Theoretical Computer Science\u00a0372(1), 115\u2013121 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"26_CR8","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R. Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching. SIAM Journal on Computing\u00a035(2), 378\u2013407 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"26_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-642-16321-0_19","volume-title":"String Processing and Information Retrieval","author":"W.-K. Hon","year":"2010","unstructured":"Hon, W.-K., Ku, T.-H., Shah, R., Thankachan, S.V., Vitter, J.S.: Faster Compressed Dictionary Matching. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 191\u2013200. Springer, Heidelberg (2010)"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Lam, T.W., Shah, R., Tam, S.L., Vitter, J.S.: Compressed Index for Dictionary Matching. In: DCC, pp. 23\u201332 (2008)","DOI":"10.1109\/DCC.2008.62"},{"key":"26_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-03784-9_8","volume-title":"String Processing and Information Retrieval","author":"W.-K. Hon","year":"2009","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: On Entropy-Compressed Text Indexing in External Memory. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 75\u201389. Springer, Heidelberg (2009)"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Sparse Suffix Trees. In: COCOON, vol.\u00a0219\u2013230 (1996)","DOI":"10.1007\/3-540-61332-3_155"},{"issue":"5","key":"26_CR13","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 Journal on Computing\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"26_CR14","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A Space-economical Suffix Tree Construction Algorithm. Journal of the ACM\u00a023(2), 262\u2013272 (1976)","journal-title":"Journal of the ACM"},{"issue":"4","key":"26_CR15","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","volume":"42","author":"Y. Nekrich","year":"2009","unstructured":"Nekrich, Y.: Orthogonal Range Searching in Linear and Almost-Linear Space. Computational Geometry\u00a042(4), 342\u2013351 (2009)","journal-title":"Computational Geometry"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets. ACM Transactions on Algorithms\u00a03(4) (2007)","DOI":"10.1145\/1290672.1290680"},{"key":"26_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1007\/978-3-540-77120-3_73","volume-title":"Algorithms and Computation","author":"T.-W. Lam","year":"2007","unstructured":"Lam, T.-W., Sung, W.-K., Tam, S.-L., Yiu, S.-M.: Space Efficient Indexes for String Matching with Don\u2019t Cares. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 846\u2013857. Springer, Heidelberg (2007)"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-642-03784-9_5","volume-title":"String Processing and Information Retrieval","author":"A. Tam","year":"2009","unstructured":"Tam, A., Wu, E., Lam, T.-W., Yiu, S.-M.: Succinct Text Indexing with Wildcards. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 39\u201350. Springer, Heidelberg (2009)"},{"key":"26_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-642-21458-5_5","volume-title":"Combinatorial Pattern Matching","author":"C. Thachuk","year":"2011","unstructured":"Thachuk, C.: Succincter Text Indexing with Wildcards. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 27\u201340. Springer, Heidelberg (2011)"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear Pattern Matching Algorithms. In: FOCS, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"5","key":"26_CR21","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of Individual Sequences via Variable Length Coding. IEEE Transactions on Information Theory\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Transactions on Information Theory"}],"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-24583-1_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,16]],"date-time":"2019-06-16T16:32:00Z","timestamp":1560702720000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24583-1_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642245824","9783642245831"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24583-1_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}