{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:34:48Z","timestamp":1758270888213},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p> We propose new algorithms for (\u03b4,\u03b3,\u03b1)-matching. In this string matching problem we are given a pattern P = p<jats:sub>0<\/jats:sub>p<jats:sub>1<\/jats:sub> \u2026 p<jats:sub>m\u22121<\/jats:sub> and a text T = t<jats:sub>0<\/jats:sub>t<jats:sub>1<\/jats:sub> \u2026 t<jats:sub>n\u22121<\/jats:sub> over some integer alphabet \u03a3 = {0\u2026\u03c3 \u2212 1}. The pattern symbol p<jats:sub>i<\/jats:sub> \u03b4-matches the text symbol t<jats:sub>j<\/jats:sub> iff |p<jats:sub>i<\/jats:sub> \u2212 t<jats:sub>j<\/jats:sub>| \u2264 \u03b4. The pattern P (\u03b4,\u03b3)-matches some text substring t<jats:sub>j<\/jats:sub> \u2026 t<jats:sub>j+m\u22121<\/jats:sub> iff for all i it holds that |p<jats:sub>i<\/jats:sub> \u2212 t<jats:sub>j+i<\/jats:sub>| \u2264 \u03b4 and \u03a3 |p<jats:sub>i<\/jats:sub> \u2212 t<jats:sub>j+i<\/jats:sub>| \u2264 \u03b3. Finally, in (\u03b4,\u03b3,\u03b1)-matching we also permit at most \u03b1-symbol gaps between each matching text symbol. The only known previous algorithm runs in O(nm) time. We give several algorithms that improve the average case up to O(n) for small \u03b1, and the worst case to [Formula: see text] or O(nm log (\u03b3)\/w), where [Formula: see text] and w is the number of bits in a machine word. The proposed algorithms can be easily modified to solve several other related problems, we explicitly consider e.g. character classes (instead of \u03b4-matching), (\u0394-limited) k-mismatches (instead of \u03b3-matching) and more general gaps, including negative ones. These find important applications in computational biology. We conclude with experimental results showing that the algorithms are very efficient in practice. <\/jats:p>","DOI":"10.1142\/s0129054108005607","type":"journal-article","created":{"date-parts":[[2008,2,20]],"date-time":"2008-02-20T04:46:31Z","timestamp":1203482791000},"page":"163-183","source":"Crossref","is-referenced-by-count":3,"title":["EFFICIENT ALGORITHMS FOR (\u03b4,\u03b3,\u03b1) AND (\u03b4, k<sub>\u0394<\/sub>, \u03b1)-MATCHING"],"prefix":"10.1142","volume":"19","author":[{"given":"KIMMO","family":"FREDRIKSSON","sequence":"first","affiliation":[{"name":"Department of Computer Science and Statistics, PO Box 111, 80101 University of Joensuu, Finland"}]},{"given":"SZYMON","family":"GRABOWSKI","sequence":"additional","affiliation":[{"name":"Technical University of \u0141\u00f3d\u017a, Computer Engineering Department, Al. Politechniki 11, 90-924 \u0141\u00f3d\u017a, Poland"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","first-page":"54","volume":"9","author":"Crochemore M.","journal-title":"Nordic Journal of Computing"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.005"},{"key":"rf5","first-page":"1","volume":"56","author":"Crochemore M.","journal-title":"Fundamenta Informaticae"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"rf9","author":"Fredriksson K.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90028-1"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786986"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.07.008"},{"key":"rf15","first-page":"299","volume":"9","author":"Mehldau G.","journal-title":"Comput. Appl. Biosci."},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69672-5"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1996.3.33"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1089\/106652703322756140"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108005607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:29:28Z","timestamp":1565177368000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108005607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2]]},"references-count":12,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1142\/S0129054108005607"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108005607","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2]]}}}