{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T10:21:01Z","timestamp":1751192461855},"reference-count":4,"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":[[2005,12]]},"abstract":"<jats:p> We present three linear algorithms for as many formulations of the problem of finding motifs with gaps. The three versions of the problem are distinct in that they assume different constraints on the size of the gaps. The outline of the algorithm is always the same, although this is adapted each time to the specific problem, while maintaining a linear time complexity with respect to the input size. The approach we suggest is based on a re-writing of the text that uses a new alphabet made of labels representing words of the original input text. The computational complexity of the algorithm allows the use of it also to find long motifs. The algorithm is in fact general enough that it could be applied to several variants of the problem other than those suggested in this paper. <\/jats:p>","DOI":"10.1142\/s0129054105003716","type":"journal-article","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T11:54:25Z","timestamp":1133524465000},"page":"1145-1154","source":"Crossref","is-referenced-by-count":21,"title":["A FIRST APPROACH TO FINDING COMMON MOTIFS WITH GAPS"],"prefix":"10.1142","volume":"16","author":[{"given":"COSTAS S.","family":"ILIOPOULOS","sequence":"first","affiliation":[{"name":"Dept. Computer Science,  King's College London, London WC2R 2LS, England"},{"name":"School of Computing, Curtin  University of Technology, GPO Box 1987 U, WA, Australia"}]},{"given":"JAMES","family":"MCHUGH","sequence":"additional","affiliation":[{"name":"New Jersey Institute of Technology  College of Computing Sciences 323 M.L.King Blvd., University Heights  Newark, NJ 07102-1982, USA"}]},{"given":"PIERRE","family":"PETERLONGO","sequence":"additional","affiliation":[{"name":"Institut Gaspard-Monge,  Universit\u00e9 de Marne-la-Vall\u00e9e, Cit\u00e9  Descartes, Champs sur Marne, 77454 Marne-la-Vall\u00e9e  CEDEX 2, France"}]},{"given":"NADIA","family":"PISANTI","sequence":"additional","affiliation":[{"name":"Department of Computer Science,  University of Pisa, Italy"}]},{"given":"WOJCIECH","family":"RYTTER","sequence":"additional","affiliation":[{"name":"New Jersey Institute of  Technology College of Computing Sciences 323 M.L.King Blvd.,  University Heights Newark, NJ 07102-1982, USA"}]},{"given":"MARIE-FRANCE","family":"SAGOT","sequence":"additional","affiliation":[{"name":"Inria Rh\u00f4ne-Alpes,  UMR 5558 Biom\u00e9trie et Biologie \u00c9volutive  Universit\u00e9 Claude Bernard, Lyon 1. 43, Bd du 11  novembre 1918 69622 Villeurbanne cedex, France"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"Text algorithms","author":"Crochemore M.","year":"1994"},{"key":"rf2","first-page":"73","volume":"11","author":"Crawford T.","journal-title":"Computing in Musicology"},{"key":"rf3","first-page":"137","author":"Farach M.","journal-title":"Foundations of Computer Science (FOCS '97)"},{"key":"rf4","volume-title":"Handbook of Exact String Matching Algorithms","author":"Charras C.","year":"2004"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003716","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:29:07Z","timestamp":1565191747000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003716"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":4,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1142\/S0129054105003716"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003716","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}