{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:42Z","timestamp":1760202522105},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540369257"},{"type":"electronic","value":"9783540369264"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11809678_17","type":"book-chapter","created":{"date-parts":[[2006,8,15]],"date-time":"2006-08-15T13:41:33Z","timestamp":1155649293000},"page":"146-155","source":"Crossref","is-referenced-by-count":25,"title":["Finding Patterns with Variable Length Gaps or Don\u2019t Cares"],"prefix":"10.1007","author":[{"given":"M. Sohel","family":"Rahman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inbok","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manal","family":"Mohamed","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William F.","family":"Smyth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A. Aho","year":"1975","unstructured":"Aho, A., Corasick, M.: Efficient string matching: an aid to bibliographic search. Communications of the ACM\u00a018, 333\u2013340 (1975)","journal-title":"Communications of the ACM"},{"key":"17_CR2","first-page":"1353","volume":"79","author":"T. Akutsu","year":"1996","unstructured":"Akutsu, T.: Approximate string matching with variable length don\u2019t care characters. IEICE Trans. Information and Systems\u00a0E79-D, 1353\u20131354 (1996)","journal-title":"IEICE Trans. Information and Systems"},{"key":"17_CR3","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. In: Proceedings of the Symposium on Discrete Algorithms (SODA 2000), pp. 794\u2013803 (2000)"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/135239.135243","volume":"35","author":"R. Baeza-Yates","year":"1992","unstructured":"Baeza-Yates, R., Gonnet, G.: A new approach to text searching. Communications of the ACM\u00a035, 74\u201382 (1992)","journal-title":"Communications of the ACM"},{"key":"17_CR5","unstructured":"Cole, R., Hariharan, R.: Approximate string matching: a faster simpler algorithm. In: Proceedings of the Symposium on Discrete Algorithms (SODA 1998), pp. 463\u2013472 (1998)"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Cole, R., Hariharan, R.: Verifying candidate matches in sparse and wildcard matching. In: Proceedings of the Symposium on Theory of Computing (STOC 2002), pp. 592\u2013601 (2002)","DOI":"10.1145\/509907.509992"},{"issue":"4","key":"17_CR7","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. SIGACT News\u00a017(4), 52\u201354 (1986)","journal-title":"SIGACT News"},{"key":"17_CR8","unstructured":"Fischer, M.J., Paterson, M.S.: String matching and other products. Technical report, Massachusetts Institute of Technology, Cambridge, MA (1974)"},{"key":"17_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on strings, trees, and sequences. Cambridge University Press, Cambridge (1997)"},{"key":"17_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/3-540-45061-0_73","volume-title":"Automata, Languages and Programming","author":"J. K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work Suffix Array Construction. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 943\u2013955. Springer, Heidelberg (2003)"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-44888-8_15","volume-title":"Combinatorial Pattern Matching","author":"P. Ko","year":"2003","unstructured":"Ko, P., Aluru, S.: Space Efficient Linear Time Construction of Suffix Arrays. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 200\u2013210. Springer, Heidelberg (2003)"},{"key":"17_CR12","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., 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":"17_CR13","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"G.M. Landau","year":"1986","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching with k mismatches. Theoretical Computer Science\u00a043, 239\u2013249 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"17_CR14","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G.M. Landau","year":"1989","unstructured":"Landau, G.M., Vishkin, U.: Fast parallel and serial approximate string matching. Journal of Algorithms\u00a010(2), 157\u2013169 (1989)","journal-title":"Journal of Algorithms"},{"key":"17_CR15","unstructured":"Lee, I., Apostolico, A., Iliopoulos, C.S., Park, K.: Finding approximate occurrence of a pattern that contains gaps. In: Proceedings of the 14th Australasian Workshop on Combinatorial Algorithms (AWOCA 2003), pp. 89\u2013100 (2003)"},{"issue":"6","key":"17_CR16","doi-asserted-by":"publisher","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. Journal of Computational Biology\u00a010(6), 903\u2013923 (2003)","journal-title":"Journal of Computational Biology"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Sahinalp, S.C., Vishkin, U.: Efficient approximate and dynamic matching of patterns using a labeling paradigm. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 320\u2013328 (1996)","DOI":"10.1109\/SFCS.1996.548491"},{"key":"17_CR18","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters\u00a06, 80\u201382 (1977)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11809678_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:26:33Z","timestamp":1619508393000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11809678_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540369257","9783540369264"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11809678_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}