{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:56Z","timestamp":1759637696175,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642311543"},{"type":"electronic","value":"9783642311550"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_25","type":"book-chapter","created":{"date-parts":[[2012,6,13]],"date-time":"2012-06-13T02:21:27Z","timestamp":1339554087000},"page":"283-294","source":"Crossref","is-referenced-by-count":5,"title":["String Indexing for Patterns with Wildcards"],"prefix":"10.1007","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[]},{"given":"Hjalte Wedel","family":"Vildh\u00f8j","sequence":"additional","affiliation":[]},{"given":"S\u00f8ren","family":"Vind","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proc. 39th FOCS, pp. 534\u2013543 (1998)","DOI":"10.7146\/brics.v5i16.21956"},{"key":"25_CR2","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. In: Proc. 11th SODA, pp. 794\u2013803 (2000)"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-21458-5_26","volume-title":"Combinatorial Pattern Matching","author":"P. Bille","year":"2011","unstructured":"Bille, P., G\u00f8rtz, I.L.: Substring Range Reporting. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 299\u2013308. Springer, Heidelberg (2011)"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-642-16321-0_40","volume-title":"String Processing and Information Retrieval","author":"P. Bille","year":"2010","unstructured":"Bille, P., Li G\u00f8rtz, I., Vildh\u00f8j, H.W., Wind, D.K.: String Matching with Variable Length Gaps. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 385\u2013394. Springer, Heidelberg (2010)"},{"key":"25_CR5","unstructured":"Bucher, P., Bairoch, A.: A generalized profile syntax for biomolecular sequence motifs and its function in automatic sequence interpretation. In: Proc. 2nd ISMB, pp. 53\u201361 (1994)"},{"issue":"4","key":"25_CR6","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/j.jda.2011.04.004","volume":"9","author":"H.L. Chan","year":"2011","unstructured":"Chan, H.L., Lam, T.W., Sung, W.K., Tam, S.L., Wong, S.S.: A linear size index for approximate pattern matching. J. Disc. Algorithms\u00a09(4), 358\u2013364 (2011)","journal-title":"J. Disc. Algorithms"},{"issue":"3","key":"25_CR7","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: A new approach to query-answering. SIAM J. Comput.\u00a015(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"25_CR8","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s10115-006-0016-8","volume":"10","author":"G. Chen","year":"2006","unstructured":"Chen, G., Wu, X., Zhu, X., Arslan, A., He, Y.: Efficient string matching with wildcards and length constraints. Knowl. Inf. Sys.\u00a010(4), 399\u2013419 (2006)","journal-title":"Knowl. Inf. Sys."},{"issue":"2","key":"25_CR9","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.ipl.2006.08.002","volume":"101","author":"P. Clifford","year":"2007","unstructured":"Clifford, P., Clifford, R.: Simple deterministic wildcard matching. Inf. Process. Lett.\u00a0101(2), 53\u201354 (2007)","journal-title":"Inf. Process. Lett."},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/11880561_27","volume-title":"String Processing and Information Retrieval","author":"L.P. Coelho","year":"2006","unstructured":"Coelho, L.P., Oliveira, A.L.: Dotted Suffix Trees A Structure for Approximate Text Indexing. In: Crestani, F., Ferragina, P., Sanderson, M. (eds.) SPIRE 2006. LNCS, vol.\u00a04209, pp. 329\u2013336. Springer, Heidelberg (2006)"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proc. 36th STOC, pp. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"25_CR12","unstructured":"Cole, R., Hariharan, R.: Approximate string matching: A simpler faster algorithm. In: Proc. 9th SODA, pp. 463\u2013472 (1998)"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Cole, R., Hariharan, R.: Verifying candidate matches in sparse and wildcard matching. In: Proc. 34rd STOC, pp. 592\u2013601 (2002)","DOI":"10.1145\/509907.509992"},{"key":"25_CR14","unstructured":"Fischer, M.J., Paterson, M.S.: String-Matching and Other Products. In: Complexity of Computation, SIAM-AMS Proceedings, pp. 113\u2013125 (1974)"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a Sparse Table with O(1) Worst Case Access Time. J. ACM\u00a031, 538\u2013544 (1984)","journal-title":"J. ACM"},{"issue":"4","key":"25_CR16","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/8307.8309","volume":"17","author":"Z. Galil","year":"1986","unstructured":"Galil, Z., Giancarlo, R.: Improved string matching with k mismatches. ACM SIGACT News\u00a017(4), 52\u201354 (1986)","journal-title":"ACM SIGACT News"},{"issue":"2","key":"25_CR17","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"25_CR18","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1093\/nar\/27.1.215","volume":"27","author":"K. Hofmann","year":"1999","unstructured":"Hofmann, K., Bucher, P., Falquet, L., Bairoch, A.: The PROSITE database, its status in 1999. Nucleic Acids Res.\u00a027(1), 215\u2013219 (1999)","journal-title":"Nucleic Acids Res."},{"key":"25_CR19","unstructured":"Iliopoulos, C.S., Rahman, M.S.: Pattern matching algorithms with don\u2019t cares. In: Proc. 33rd SOFSEM, pp. 116\u2013126 (2007)"},{"key":"25_CR20","unstructured":"Kalai, A.: Efficient pattern-matching with don\u2019t cares. In: Proc. 13th SODA, pp. 655\u2013656 (2002)"},{"key":"25_CR21","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":"25_CR22","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"G. Landau","year":"1986","unstructured":"Landau, G., Vishkin, U.: Efficient string matching with k mismatches. Theoret. Comput. Sci.\u00a043, 239\u2013249 (1986)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"25_CR23","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G. Landau","year":"1989","unstructured":"Landau, G., Vishkin, U.: Fast parallel and serial approximate string matching. J. Algorithms\u00a010(2), 157\u2013169 (1989)","journal-title":"J. Algorithms"},{"key":"25_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-24583-1_14","volume-title":"String Processing and Information Retrieval","author":"M. Lewenstein","year":"2011","unstructured":"Lewenstein, M.: Indexing with Gaps. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 135\u2013143. Springer, Heidelberg (2011)"},{"issue":"4","key":"25_CR25","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1016\/j.jda.2006.11.001","volume":"5","author":"M. Maas","year":"2007","unstructured":"Maas, M., Nowak, J.: Text indexing with errors. J. Disc. Algorithms\u00a05(4), 662\u2013681 (2007)","journal-title":"J. Disc. Algorithms"},{"issue":"4","key":"25_CR26","first-page":"19","volume":"24","author":"G. Navarro","year":"2001","unstructured":"Navarro, G., Baeza-Yates, R., Sutinen, E., Tarhio, J.: Indexing methods for approximate string matching. IEEE Data Eng. Bull.\u00a024(4), 19\u201327 (2001)","journal-title":"IEEE Data Eng. Bull."},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"Sahinalp, S., Vishkin, U.: Efficient approximate and dynamic matching of patterns using a labeling paradigm. In: Proc. 37th FOCS, pp. 320\u2013328 (1996)","DOI":"10.1109\/SFCS.1996.548491"},{"key":"25_CR28","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)"},{"issue":"4","key":"25_CR29","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.jda.2010.08.002","volume":"8","author":"D. Tsur","year":"2010","unstructured":"Tsur, D.: Fast index for approximate string matching. J. Disc. Algorithms\u00a08(4), 339\u2013345 (2010)","journal-title":"J. Disc. Algorithms"},{"key":"25_CR30","unstructured":"Vildh\u00f8j, H.W., Vind, S.: String Indexing for Patterns with Wildcards. Master\u2019s thesis, Technical University of Denmark (2011), http:\/\/www.imm.dtu.dk\/~hwvi\/"},{"key":"25_CR31","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proc. 14th SWAT, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,31]],"date-time":"2025-03-31T01:29:57Z","timestamp":1743384597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}