{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:21:38Z","timestamp":1725571298975},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175138"},{"type":"electronic","value":"9783642175145"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-17514-5_2","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T20:09:23Z","timestamp":1291406963000},"page":"13-24","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Indexes for the Positional Pattern Matching Problem and Two Related Problems over Small Alphabets"],"prefix":"10.1007","author":[{"given":"Chih-Chiang","family":"Yu","sequence":"first","affiliation":[]},{"given":"Biing-Feng","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Chung-Chin","family":"Kuo","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","unstructured":"Bentley, J.L.: Solutions to Klee\u2019s rectangle problems. Department of Computer Science, Carnegie Mellon University (1977) (manuscript)"},{"issue":"2","key":"2_CR2","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/jpdc.1994.1083","volume":"22","author":"A.A. Bertossi","year":"1994","unstructured":"Bertossi, A.A., Lodi, E.: Parallel string matching with variable length don\u2019t cares. J. Parallel Distrib. Comput.\u00a022(2), 229\u2013234 (1994)","journal-title":"J. Parallel Distrib. Comput."},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., J\u00f8rgensen, A.G.: Data structures for range median queries. In: Dong, Y., Du, D.-Z., Ibarra, O.H. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 822\u2013831. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-10631-6_83"},{"issue":"3","key":"2_CR4","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput.\u00a017(3), 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"key":"2_CR5","unstructured":"Clark, D.: Compact pat trees. PhD Thesis, Univ. Waterloo (1996)"},{"key":"2_CR6","unstructured":"Crochemore, M., Iliopoulos, C.S., Kubica, M., Rahman, M.S., Walen, T.: Improved algorithms for the range next value problem and applications. In: 25th Annual Symposium on Theoretical Aspects of Computer Science, pp. 205\u2013216 (2008)"},{"key":"2_CR7","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"},{"key":"2_CR8","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841\u2013850 (2003)"},{"issue":"1","key":"2_CR9","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T. Hagerup","year":"2001","unstructured":"Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms\u00a041(1), 69\u201385 (2001)","journal-title":"J. Algorithms"},{"key":"2_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/3-540-45452-7_14","volume-title":"Combinatorial Pattern Matching","author":"S. Inenaga","year":"2002","unstructured":"Inenaga, S., Takeda, M., Shinohara, A., Hoshino, H., Arikawa, S.: The minimum DAWG for all suffixes of a string and its applications. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol.\u00a02373, pp. 153\u2013167. Springer, Heidelberg (2002)"},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/978-3-540-73951-7_54","volume-title":"Algorithms and Data Structures","author":"O. Keller","year":"2007","unstructured":"Keller, O., Kopelowitz, T., Lewenstein, M.: Range non-overlapping indexing and successive list indexing. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 625\u2013636. Springer, Heidelberg (2007)"},{"issue":"1-2","key":"2_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0304-3975(97)88195-9","volume":"178","author":"G. Kucherov","year":"1997","unstructured":"Kucherov, G., Rusinowitch, M.: Matching a set of strings with variable length don\u2019t cares. Theor. Comput. Sci.\u00a0178(1-2), 129\u2013154 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR13","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)"},{"issue":"3","key":"2_CR14","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.tcs.2007.07.013","volume":"387","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Rank and Select Revisited and Extended. Theor. Comput. Sci.\u00a0387(3), 332\u2013347 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"2_CR15","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. J. ACM\u00a023(2), 262\u2013272 (1976)","journal-title":"J. ACM"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Munro, J.I.: Tables. In: 16th Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 37\u201342 (1996)","DOI":"10.1007\/3-540-62034-6_35"},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-642-82456-2_2","volume":"12","author":"R.Y. Pinter","year":"1985","unstructured":"Pinter, R.Y.: Efficient string matching with don\u2019t-cares. Combinatorial Algorithms on Words\u00a012, 11\u201329 (1985)","journal-title":"Combinatorial Algorithms on Words"},{"key":"2_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Heidelberg (1985)"},{"key":"2_CR19","unstructured":"Sustik, M.A., Moore, J.S.: String searching over small alphabets. Technical Report TR-07-62, Department of Computer Sciences, University of Texas at Austin (2007)"},{"issue":"1","key":"2_CR20","first-page":"47","volume":"91","author":"R. Thathoo","year":"2006","unstructured":"Thathoo, R., Virmani, A., Lakshmi, S.S., Balakrishnan, N., Sekar, K.: TVSBS: A fast exact pattern matching algorithm for biological sequences. Current Sciences\u00a091(1), 47\u201353 (2006)","journal-title":"Current Sciences"},{"issue":"3","key":"2_CR21","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/S0097539797322425","volume":"29","author":"D.E. Willard","year":"2000","unstructured":"Willard, D.E.: Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput.\u00a029(3), 1030\u20131049 (2000)","journal-title":"SIAM J. Comput."},{"key":"2_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-642-02882-3_11","volume-title":"Computing and Combinatorics","author":"C.-C. Yu","year":"2009","unstructured":"Yu, C.-C., Hon, W.-K., Wang, B.-F.: Efficient data structures for the orthogonal range successor problem. In: Ngo, H.Q. (ed.) COCOON 2009. LNCS, vol.\u00a05609, pp. 96\u2013105. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17514-5_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T19:49:16Z","timestamp":1559850556000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17514-5_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175138","9783642175145"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17514-5_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}