{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:45:05Z","timestamp":1773276305654,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,9,6]],"date-time":"2013-09-06T00:00:00Z","timestamp":1378425600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,7]]},"DOI":"10.1007\/s00224-013-9498-4","type":"journal-article","created":{"date-parts":[[2013,9,5]],"date-time":"2013-09-05T03:15:24Z","timestamp":1378350924000},"page":"41-60","source":"Crossref","is-referenced-by-count":14,"title":["String Indexing for Patterns with Wildcards"],"prefix":"10.1007","volume":"55","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hjalte Wedel","family":"Vildh\u00f8j","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00f8ren","family":"Vind","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,9,6]]},"reference":[{"key":"9498_CR1","first-page":"534","volume-title":"Proc. 39th FOCS","author":"S. Alstrup","year":"1998","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proc. 39th FOCS, pp. 534\u2013543 (1998)"},{"issue":"2","key":"9498_CR2","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0196-6774(03)00097-X","volume":"50","author":"A. Amir","year":"2004","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. J.\u00a0Algorithms 50(2), 257\u2013275 (2004)","journal-title":"J.\u00a0Algorithms"},{"key":"9498_CR3","first-page":"154","volume-title":"Proc. 20th CPM","author":"D. Belazzougui","year":"2009","unstructured":"Belazzougui, D.: Faster and space-optimal edit distance \u201c1\u201d dictionary. In: Proc. 20th CPM, pp. 154\u2013167 (2009)"},{"key":"9498_CR4","first-page":"299","volume-title":"Proc. 22nd CPM","author":"P. Bille","year":"2011","unstructured":"Bille, P., G\u00f8rtz, I.L.: Substring range reporting. In: Proc. 22nd CPM, pp. 299\u2013308 (2011)"},{"key":"9498_CR5","first-page":"385","volume-title":"Proc. 17th SPIRE","author":"P. Bille","year":"2010","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H., Wind, D.: String matching with variable length gaps. In: Proc. 17th SPIRE, pp. 385\u2013394 (2010)"},{"key":"9498_CR6","first-page":"53","volume-title":"Proc. 2nd ISMB","author":"P. Bucher","year":"1994","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":"9498_CR7","doi-asserted-by":"crossref","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. Discrete Algorithms 9(4), 358\u2013364 (2011)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"9498_CR8","doi-asserted-by":"crossref","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. 15(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9498_CR9","doi-asserted-by":"crossref","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. Syst. 10(4), 399\u2013419 (2006)","journal-title":"Knowl. Inf. Syst."},{"issue":"2","key":"9498_CR10","doi-asserted-by":"crossref","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. 101(2), 53\u201354 (2007)","journal-title":"Inf. Process. Lett."},{"key":"9498_CR11","first-page":"329","volume-title":"Proc. 13th SPIRE","author":"L. Coelho","year":"2006","unstructured":"Coelho, L., Oliveira, A.: Dotted suffix trees a structure for approximate text indexing. In: Proc. 13th SPIRE, pp. 329\u2013336 (2006)"},{"issue":"6","key":"9498_CR12","doi-asserted-by":"crossref","first-page":"1761","DOI":"10.1137\/S0097539700370527","volume":"31","author":"R. Cole","year":"2002","unstructured":"Cole, R., Hariharan, R.: Approximate string matching: a simpler faster algorithm. SIAM J. Comput. 31(6), 1761\u20131782 (2002)","journal-title":"SIAM J. Comput."},{"key":"9498_CR13","first-page":"592","volume-title":"Proc. 34rd STOC","author":"R. Cole","year":"2002","unstructured":"Cole, R., Hariharan, R.: Verifying candidate matches in sparse and wildcard matching. In: Proc. 34rd STOC, pp. 592\u2013601 (2002)"},{"key":"9498_CR14","first-page":"91","volume-title":"Proc. 36th STOC","author":"R. Cole","year":"2004","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)"},{"key":"9498_CR15","first-page":"113","volume-title":"Complexity of Computation, SIAM-AMS Proceedings","author":"M.J. Fischer","year":"1974","unstructured":"Fischer, M.J., Paterson, M.S.: String-matching and other products. In: Complexity of Computation, SIAM-AMS Proceedings, pp. 113\u2013125 (1974)"},{"key":"9498_CR16","doi-asserted-by":"crossref","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 31, 538\u2013544 (1984)","journal-title":"J. ACM"},{"issue":"4","key":"9498_CR17","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s10791-008-9054-z","volume":"11","author":"K. Fredriksson","year":"2008","unstructured":"Fredriksson, K., Grabowski, S.: Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance. Inf. Retr. 11(4), 335\u2013357 (2008)","journal-title":"Inf. Retr."},{"key":"9498_CR18","first-page":"338","volume-title":"Proc. 3rd LATA","author":"K. Fredriksson","year":"2009","unstructured":"Fredriksson, K., Grabowski, S.: Nested counters in bit-parallel string matching. In: Proc. 3rd LATA, pp. 338\u2013349 (2009)"},{"issue":"4","key":"9498_CR19","doi-asserted-by":"crossref","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. SIGACT News 17(4), 52\u201354 (1986)","journal-title":"SIGACT News"},{"key":"9498_CR20","first-page":"366","volume-title":"Proc. 15th STACS","author":"T. Hagerup","year":"1998","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: Proc. 15th STACS, pp. 366\u2013398 (1998)"},{"issue":"2","key":"9498_CR21","doi-asserted-by":"crossref","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. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9498_CR22","doi-asserted-by":"crossref","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. 27(1), 215\u2013219 (1999)","journal-title":"Nucleic Acids Res."},{"key":"9498_CR23","first-page":"116","volume-title":"Proc. 33rd SOFSEM","author":"C.S. Iliopoulos","year":"2007","unstructured":"Iliopoulos, C.S., Rahman, M.S.: Pattern matching algorithms with don\u2019t cares. In: Proc. 33rd SOFSEM, pp. 116\u2013126 (2007)"},{"key":"9498_CR24","first-page":"655","volume-title":"Proc. 13th SODA","author":"A. Kalai","year":"2002","unstructured":"Kalai, A.: Efficient pattern-matching with don\u2019t cares. In: Proc. 13th SODA, pp. 655\u2013656 (2002)"},{"key":"9498_CR25","first-page":"846","volume-title":"Proc. 18th ISAAC","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: Proc. 18th ISAAC, pp. 846\u2013857 (2007)"},{"key":"9498_CR26","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 43, 239\u2013249 (1986)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9498_CR27","doi-asserted-by":"crossref","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 10(2), 157\u2013169 (1989)","journal-title":"J. Algorithms"},{"key":"9498_CR28","first-page":"135","volume-title":"Proc. 18th SPIRE","author":"M. Lewenstein","year":"2011","unstructured":"Lewenstein, M.: Indexing with gaps. In: Proc. 18th SPIRE, pp. 135\u2013143 (2011)"},{"issue":"4","key":"9498_CR29","doi-asserted-by":"crossref","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. Discrete Algorithms 5(4), 662\u2013681 (2007)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"9498_CR30","first-page":"299","volume":"9","author":"G. Mehldau","year":"1993","unstructured":"Mehldau, G., Myers, G.: A system for pattern matching applications on biosequences. Comput. Appl. Biosci. 9(3), 299\u2013314 (1993)","journal-title":"Comput. Appl. Biosci."},{"issue":"8","key":"9498_CR31","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1089\/cmb.2005.12.1065","volume":"12","author":"M. Morgante","year":"2005","unstructured":"Morgante, M., Policriti, A., Vitacolonna, N., Zuccolo, A.: Structured motifs search. J. Comput. Biol. 12(8), 1065\u20131082 (2005)","journal-title":"J. Comput. Biol."},{"issue":"1","key":"9498_CR32","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1089\/cmb.1996.3.33","volume":"3","author":"E. Myers","year":"1996","unstructured":"Myers, E.: Approximate matching of network expressions with spacers. J. Comput. Biol. 3(1), 33\u201351 (1996)","journal-title":"J. Comput. Biol."},{"issue":"6","key":"9498_CR33","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1089\/106652703322756140","volume":"10","author":"G. Navarro","year":"2003","unstructured":"Navarro, G., Raffinot, M.: Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching. J. Comput. Biol. 10(6), 903\u2013923 (2003)","journal-title":"J. Comput. Biol."},{"issue":"4","key":"9498_CR34","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. 24(4), 19\u201327 (2001)","journal-title":"IEEE Data Eng. Bull."},{"key":"9498_CR35","first-page":"146","volume-title":"Proc. 12th COCOON","author":"M.S. Rahman","year":"2006","unstructured":"Rahman, M.S., Iliopoulos, C.S., Lee, I., Mohamed, M., Smyth, W.F.: Finding patterns with variable length gaps or don\u2019t cares. In: Proc. 12th COCOON, pp. 146\u2013155 (2006)"},{"key":"9498_CR36","first-page":"320","volume-title":"Proc. 37th FOCS","author":"S. Sahinalp","year":"1996","unstructured":"Sahinalp, S., Vishkin, U.: Efficient approximate and dynamic matching of patterns using a labeling paradigm. In: Proc. 37th FOCS, pp. 320\u2013328 (1996)"},{"key":"9498_CR37","first-page":"39","volume-title":"Proc. 16th SPIRE","author":"A. Tam","year":"2009","unstructured":"Tam, A., Wu, E., Lam, T., Yiu, S.: Succinct text indexing with wildcards. In: Proc. 16th SPIRE, pp. 39\u201350 (2009)"},{"issue":"4","key":"9498_CR38","doi-asserted-by":"crossref","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. Discrete Algorithms 8(4), 339\u2013345 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"9498_CR39","first-page":"1","volume-title":"Proc. 14th SWAT","author":"P. Weiner","year":"1973","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proc. 14th SWAT, pp. 1\u201311 (1973)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9498-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9498-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9498-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:25Z","timestamp":1558698865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9498-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,6]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["9498"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9498-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,6]]}}}