{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T10:42:40Z","timestamp":1775644960313,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2017,9,18]],"date-time":"2017-09-18T00:00:00Z","timestamp":1505692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2017,12,15]]},"abstract":"<jats:p>\n            We consider approximate string matching of a circular pattern consisting of the rotations of a pattern of length\n            <jats:italic>m<\/jats:italic>\n            . From SBNDM and Tuned Shift-Add, we derive a sublinear-time algorithm for searching a noncircular pattern with\n            <jats:italic>k<\/jats:italic>\n            allowed mismatches, which is extended to the problem of approximate circular pattern matching with\n            <jats:italic>k<\/jats:italic>\n            mismatches. We prove that the presented algorithms are average-optimal for\n            <jats:italic>m<\/jats:italic>\n            \u22c5\u2308log\n            <jats:sub>2<\/jats:sub>\n            (\n            <jats:italic>k<\/jats:italic>\n            +1)+1 \u2309 =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>w<\/jats:italic>\n            ), where\n            <jats:italic>w<\/jats:italic>\n            is the size of the computer word in bits. Experiments conducted under the aforementioned condition show that the new\n            <jats:italic>k<\/jats:italic>\n            -mismatches algorithm for circular strings outperforms previous solutions in practice. In particular, our algorithm is the first nonfiltering method for approximate circular string matching in sublinear average time, which makes it more suitable than earlier filtering methods for high error levels\n            <jats:italic>k<\/jats:italic>\n            \/\n            <jats:italic>m<\/jats:italic>\n            and small alphabets.\n          <\/jats:p>","DOI":"10.1145\/3129536","type":"journal-article","created":{"date-parts":[[2017,9,18]],"date-time":"2017-09-18T12:20:54Z","timestamp":1505737254000},"page":"1-12","source":"Crossref","is-referenced-by-count":5,"title":["Bit-Parallel Approximate Matching of Circular Strings with\n            <i>k<\/i>\n            Mismatches"],"prefix":"10.1145","volume":"22","author":[{"given":"Tommi","family":"Hirvola","sequence":"first","affiliation":[{"name":"Aalto University, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorma","family":"Tarhio","sequence":"additional","affiliation":[{"name":"Aalto University, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Md. Aashikur Rahman Azim Costas S. Iliopoulos M. Sohel Rahman and M. Samiruzzaman. 2015. SimpLiFiCPM: A simple and lightweight filter-based algorithm for circular pattern matching. International Journal of Genomics (2015).  Md. Aashikur Rahman Azim Costas S. Iliopoulos M. Sohel Rahman and M. Samiruzzaman. 2015. SimpLiFiCPM: A simple and lightweight filter-based algorithm for circular pattern matching. International Journal of Genomics (2015).","DOI":"10.1155\/2015\/259320"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNB.2016.2542062"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135243"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-9-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-15579-1_6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1002445"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(93)90177-X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1875616.1875634"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/647814.738431"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 29th Workshop on Combinatorial Mathematics and Computation Theory. 18--27","author":"Chen Kuei-Hao"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of PSC 2014, Prague Stringology Conference. 71--83","author":"\u010eurian Branislav","year":"2014"},{"key":"e_1_2_1_12_1","volume-title":"SMART: A string matching algorithm research tool","author":"Faro Simone","year":"2011"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00982-2_29"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005813.1041513"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397002939"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.192484"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/262228"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.002"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_27"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"ThienLuan Ho Seung-Rohk Oh and HyunJin Kim. 2016. Circular bit-vector-mismatches: A new approximate circular string matching with k-mismatches. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E99-A 9 (2016) 1726--1729.  ThienLuan Ho Seung-Rohk Oh and HyunJin Kim. 2016. Circular bit-vector-mismatches: A new approximate circular string matching with k-mismatches. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E99-A 9 (2016) 1726--1729.","DOI":"10.1587\/transfun.E99.A.1726"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2010.08.001"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxr126"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkn679"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2000.906217"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.411"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384246"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.1996.546859"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39984-1_7"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-02309-0_59"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222018"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3129536","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3129536","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:32Z","timestamp":1750217432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3129536"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,18]]},"references-count":31,"alternative-id":["10.1145\/3129536"],"URL":"https:\/\/doi.org\/10.1145\/3129536","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,18]]}}}