{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:59:23Z","timestamp":1725551963138},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642124754"},{"type":"electronic","value":"9783642124761"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12476-1_15","type":"book-chapter","created":{"date-parts":[[2010,4,8]],"date-time":"2010-04-08T13:46:37Z","timestamp":1270734397000},"page":"210-220","source":"Crossref","is-referenced-by-count":1,"title":["Approximate String Matching with Reduced Alphabet"],"prefix":"10.1007","author":[{"given":"Leena","family":"Salmela","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorma","family":"Tarhio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-3","key":"15_CR1","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E. Ukkonen","year":"1985","unstructured":"Ukkonen, E.: Algorithms for approximate string matching. Information and Control\u00a064(1-3), 100\u2013118 (1985)","journal-title":"Information and Control"},{"issue":"1","key":"15_CR2","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","volume":"6","author":"E. Ukkonen","year":"1985","unstructured":"Ukkonen, E.: Finding approximate patterns in strings. J. Algorithms\u00a06(1), 132\u2013137 (1985)","journal-title":"J. Algorithms"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/3-540-54345-7_67","volume-title":"Mathematical Foundations of Computer Science 1991","author":"P. Jokinen","year":"1991","unstructured":"Jokinen, P., Ukkonen, E.: Two algorithms for approximate string matching in static texts. In: Tarlecki, A. (ed.) MFCS 1991. LNCS, vol.\u00a0520, pp. 240\u2013248. Springer, Heidelberg (1991)"},{"issue":"1","key":"15_CR4","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"E. Ukkonen","year":"1992","unstructured":"Ukkonen, E.: Approximate string matching with q-grams and maximal matches. Theor. Comput. Sci.\u00a092(1), 191\u2013211 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/BFb0029808","volume-title":"Combinatorial Pattern Matching","author":"E. Ukkonen","year":"1993","unstructured":"Ukkonen, E.: Approximate string-matching over suffix trees. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) CPM 1993. LNCS, vol.\u00a0684, pp. 228\u2013242. Springer, Heidelberg (1993)"},{"issue":"5","key":"15_CR6","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/BF01769703","volume":"10","author":"E. Ukkonen","year":"1993","unstructured":"Ukkonen, E., Wood, D.: Approximate string matching with suffix automata. Algorithmica\u00a010(5), 353\u2013364 (1993)","journal-title":"Algorithmica"},{"issue":"2","key":"15_CR7","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1137\/0222018","volume":"22","author":"J. Tarhio","year":"1993","unstructured":"Tarhio, J., Ukkonen, E.: Approximate Boyer\u2013Moore string matching. SIAM J. Comput.\u00a022(2), 243\u2013260 (1993)","journal-title":"SIAM J. Comput."},{"issue":"12","key":"15_CR8","doi-asserted-by":"publisher","first-page":"1439","DOI":"10.1002\/(SICI)1097-024X(199612)26:12<1439::AID-SPE71>3.0.CO;2-1","volume":"26","author":"P. Jokinen","year":"1996","unstructured":"Jokinen, P., Tarhio, J., Ukkonen, E.: A comparison of approximate string matching algorithms. Software\u2013Pract. Exp.\u00a026(12), 1439\u20131458 (1996)","journal-title":"Software\u2013Pract. Exp."},{"key":"15_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/3-540-45452-7_20","volume-title":"Combinatorial Pattern Matching","author":"K. Fredriksson","year":"2002","unstructured":"Fredriksson, K., Navarro, G., Ukkonen, E.: Optimal exact and fast approximate two dimensional pattern matching allowing rotations. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol.\u00a02373, pp. 235\u2013248. Springer, Heidelberg (2002)"},{"issue":"3-4","key":"15_CR10","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S1570-8667(03)00032-7","volume":"1","author":"J. K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Navarro, G., Ukkonen, E.: Approximate string matching on Ziv\u2013Lempel compressed text. J. Discrete Algorithms\u00a01(3-4), 313\u2013338 (2003)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"15_CR11","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s00453-002-1005-2","volume":"35","author":"V. M\u00e4kinen","year":"2003","unstructured":"M\u00e4kinen, V., Ukkonen, E., Navarro, G.: Approximate matching of run-length compressed strings. Algorithmica\u00a035(4), 347\u2013369 (2003)","journal-title":"Algorithmica"},{"issue":"6","key":"15_CR12","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1002\/spe.4380100608","volume":"10","author":"R.N. Horspool","year":"1980","unstructured":"Horspool, R.N.: Practical fast searching in strings. Software\u2013Pract. Exp.\u00a010(6), 501\u2013506 (1980)","journal-title":"Software\u2013Pract. Exp."},{"issue":"10","key":"15_CR13","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R.S. Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commun. ACM\u00a020(10), 762\u2013772 (1977)","journal-title":"Commun. ACM"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Salmela, L., Tarhio, J., Kalsi, P.: Approximate Boyer\u2013Moore string matching for small alphabets. Algorithmica (in press)","DOI":"10.1007\/s00453-009-9286-3"},{"issue":"2","key":"15_CR15","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Research and Development\u00a031(2), 249\u2013260 (1987)","journal-title":"IBM J. Research and Development"},{"issue":"9","key":"15_CR16","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1145\/66451.66459","volume":"32","author":"R. Zhu","year":"1989","unstructured":"Zhu, R., Takaoka, T.: A technique for two-dimensional pattern matching. Commun. ACM\u00a032(9), 1110\u20131120 (1989)","journal-title":"Commun. ACM"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/3-540-61258-0_7","volume-title":"Combinatorial Pattern Matching","author":"R. Muth","year":"1996","unstructured":"Muth, R., Manber, U.: Approximate multiple strings search. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 75\u201386. Springer, Heidelberg (1996)"},{"issue":"2","key":"15_CR18","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1137\/S0097539794275872","volume":"29","author":"J. K\u00e4rkk\u00e4inen","year":"1999","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Two- and higher-dimensional pattern matching in optimal expected time. SIAM J. Comput.\u00a029(2), 571\u2013589 (1999)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"15_CR19","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1016\/0167-8655(96)00055-4","volume":"17","author":"J. Tarhio","year":"1996","unstructured":"Tarhio, J.: A sublinear algorithm for two-dimensional string matching. Pattern Recogn. Lett.\u00a017(8), 833\u2013838 (1996)","journal-title":"Pattern Recogn. Lett."},{"issue":"3","key":"15_CR20","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1016\/j.jda.2007.11.001","volume":"6","author":"L. Salmela","year":"2008","unstructured":"Salmela, L., Tarhio, J.: Fast parameterized matching with q-grams. J. Discrete Algorithms\u00a06(3), 408\u2013419 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"6","key":"15_CR21","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/j.ipl.2007.01.002","volume":"102","author":"T. Lecroq","year":"2007","unstructured":"Lecroq, T.: Fast exact string matching algorithms. Inf. Process. Lett.\u00a0102(6), 229\u2013235 (2007)","journal-title":"Inf. Process. Lett."},{"key":"15_CR22","unstructured":"Wu, S., Manber, U.: A fast algorithm for multi-pattern searching. Technical report, Dept. of Computer Science, U. of Arizona (1994)"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Kim, S.: A new string-pattern matching algorithm using partitioning and hashing efficiently. J. Exp. Algorithmics\u00a04(2) (1999)","DOI":"10.1145\/347792.347803"},{"issue":"4","key":"15_CR24","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0020-0190(03)00296-5","volume":"87","author":"K. Fredriksson","year":"2003","unstructured":"Fredriksson, K.: Shift-or string matching with super-alphabets. Inf. Process. Lett.\u00a087(4), 201\u2013204 (2003)","journal-title":"Inf. Process. Lett."},{"key":"15_CR25","first-page":"29","volume-title":"Proc. ALENEX 2009","author":"B. \u010eurian","year":"2009","unstructured":"\u010eurian, B., Holub, J., Peltola, H., Tarhio, J.: Tuning BNDM with q-grams. In: Proc. ALENEX 2009, pp. 29\u201337. SIAM, Philadelphia (2009)"},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"Salmela, L., Tarhio, J., Kyt\u00f6joki, J.: Multipattern string matching with q-grams. J. Exp. Algorithmics\u00a011 (2006)","DOI":"10.1145\/1187436.1187438"},{"issue":"6","key":"15_CR27","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1142\/S0129054105003698","volume":"16","author":"M. Fontaine","year":"2005","unstructured":"Fontaine, M., Burkhardt, S., K\u00e4rkk\u00e4inen, J.: BDD-based analysis of gapped q-gram filters. Int. J. Found. Comput. Sci.\u00a016(6), 1121\u20131134 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"15_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/11575832_42","volume-title":"String Processing and Information Retrieval","author":"K. Fredriksson","year":"2005","unstructured":"Fredriksson, K., Grabowski, S.: Practical and optimal string matching. In: Consens, M.P., Navarro, G. (eds.) SPIRE 2005. LNCS, vol.\u00a03772, pp. 376\u2013387. Springer, Heidelberg (2005)"},{"issue":"1","key":"15_CR29","first-page":"67","volume":"38","author":"T. Berry","year":"2002","unstructured":"Berry, T., Ravindran, S.: Tuning the Zhu\u2013Takaoka string matching algorithm and experimental results. Kybernetika\u00a038(1), 67\u201380 (2002)","journal-title":"Kybernetika"},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"Fredriksson, K., Navarro, G.: Average-optimal single and multiple approximate string matching. J. Exp. Algorithmics\u00a09 (2004)","DOI":"10.1145\/1005813.1041513"},{"key":"15_CR31","first-page":"487","volume":"194","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradzev, I.A.: On economic construction of the transitive closure of a directed graph. Doklady Academi Nauk SSSR 194, 487\u2013488 (in Russian); English translation in Soviet Mathematics Doklady 11, 1209\u20131210 (1970)","journal-title":"Doklady Academi Nauk SSSR"},{"issue":"1","key":"15_CR32","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W.J. Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.S.: A faster algorithm for computing string edit distances. J. Comput. Syst. Sci.\u00a020(1), 18\u201331 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/11496656_8","volume-title":"Combinatorial Pattern Matching","author":"Z. Liu","year":"2005","unstructured":"Liu, Z., Chen, X., Borneman, J., Jiang, T.: A fast algorithm for approximate string matching on gene sequences. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol.\u00a03537, pp. 79\u201390. Springer, Heidelberg (2005)"},{"key":"15_CR34","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"1","key":"15_CR35","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0020-0190(96)00083-X","volume":"59","author":"R. Baeza-Yates","year":"1996","unstructured":"Baeza-Yates, R., Perleberg, C.: Fast and practical approximate string matching. Inf. Process. Lett.\u00a059(1), 21\u201327 (1996)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12476-1_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:54:27Z","timestamp":1606186467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12476-1_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642124754","9783642124761"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12476-1_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}