{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T10:40:31Z","timestamp":1695724831694},"reference-count":15,"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 study the fully compressed pattern matching problem (FCPM problem): Given [Formula: see text] and [Formula: see text] which are descriptions of text T and pattern P respectively, find the occurrences of P in Twithout decompressing[Formula: see text]or[Formula: see text]. This problem is rather challenging since patterns are also given in a compressed form. In this paper we present an FCPM algorithm for simple collage systems. Collage systems are a general framework representing various kinds of dictionary-based compressions in a uniform way, and simple collage systems are a subclass that includes LZW and LZ78 compressions. Collage systems are of the form [Formula: see text], where [Formula: see text] is a dictionary and [Formula: see text] is a sequence of variables from [Formula: see text]. Our FCPM algorithm performs in [Formula: see text] time, where [Formula: see text] and [Formula: see text]. This is faster than the previous best result of O(m<jats:sup>2<\/jats:sup>n<jats:sup>2<\/jats:sup>) time. <\/jats:p>","DOI":"10.1142\/s0129054105003728","type":"journal-article","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T11:54:25Z","timestamp":1133524465000},"page":"1155-1166","source":"Crossref","is-referenced-by-count":1,"title":["A FULLY COMPRESSED PATTERN MATCHING ALGORITHM FOR SIMPLE COLLAGE SYSTEMS"],"prefix":"10.1142","volume":"16","author":[{"given":"SHUNSUKE","family":"INENAGA","sequence":"first","affiliation":[{"name":"Department of Informatics,  Kyushu University 33, Fukuoka 812-8581, Japan"}]},{"given":"AYUMI","family":"SHINOHARA","sequence":"additional","affiliation":[{"name":"Graduate School of Information  Sciences, Tohoku University, Sendai 980-8579, Japan"}]},{"given":"MASAYUKI","family":"TAKEDA","sequence":"additional","affiliation":[{"name":"Department of Informatics,  Kyushu University 33, Fukuoka 812-8581, Japan"},{"name":"SORST, Japan Science and  Technology Agency (JST), Japan"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0023"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90112-0"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009202"},{"key":"rf5","volume":"12","author":"Gage P.","journal-title":"The C Users Journal"},{"key":"rf10","first-page":"172","volume":"4","author":"Karpinski M.","journal-title":"Nord. J. Comput."},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00426-7"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.4310\/CIS.2002.v2.n1.a2"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1109\/18.850665"},{"key":"rf18","first-page":"187","volume":"1","author":"Miyazaki M.","journal-title":"J. Discrete Algorithms"},{"key":"rf19","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1613\/jair.374","volume":"7","author":"Nevill-Manning C.","journal-title":"J. Artificial Intelligence Research"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322346"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1984.1659158"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003728","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:29:10Z","timestamp":1565191750000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003728"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":15,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1142\/S0129054105003728"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003728","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}