{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T16:53:28Z","timestamp":1768582408302,"version":"3.49.0"},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p> We study the problem of finding all maximal approximate gapped palindromes in a string. More specifically, given a string S of length n, a parameter q \u2265 0 and a threshold k &gt; 0, the problem is to identify all substrings in S of the form uvw such that (1) the Levenshtein distance between u<jats:sup>r<\/jats:sup> and w is at most k, where u<jats:sup>r<\/jats:sup> is the reverse of u and (2) v is a string of length q. The best previous work requires O(k<jats:sup>2<\/jats:sup>n) time. In this paper, we propose an O(kn)-time algorithm for this problem by utilizing an incremental string comparison technique. It turns out that the core technique actually solves a more general incremental string comparison problem that allows the insertion, deletion, and substitution of multiple symbols. <\/jats:p>","DOI":"10.1142\/s0129054110007647","type":"journal-article","created":{"date-parts":[[2010,11,24]],"date-time":"2010-11-24T08:39:03Z","timestamp":1290587943000},"page":"925-939","source":"Crossref","is-referenced-by-count":9,"title":["FINDING ALL APPROXIMATE GAPPED PALINDROMES"],"prefix":"10.1142","volume":"21","author":[{"given":"PING-HUI","family":"HSU","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan 106, Taiwan"}]},{"given":"KUAN-YU","family":"CHEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan 106, Taiwan"}]},{"given":"KUN-MAO","family":"CHAO","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan 106, Taiwan"},{"name":"Graduate Institute of Biomedical Electronics and Bioinformatics, National Taiwan University, Taipei, Taiwan 106, Taiwan"},{"name":"Graduate Institute of Networking and Multimedia, National Taiwan University, Taipei, Taiwan 106, Taiwan"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","volume-title":"Sequence Comparison: Theory and Methods","author":"Chao K. M.","year":"2009"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gni135"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.09.015"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1137\/0219067"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.075"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264810"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.016"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(01)00179-0"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90023-9"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206331"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1101\/gr.2542904"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054110007647","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:24:09Z","timestamp":1565191449000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054110007647"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":14,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1142\/S0129054110007647"],"URL":"https:\/\/doi.org\/10.1142\/s0129054110007647","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}