{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T21:51:44Z","timestamp":1771883504241,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,1,13]],"date-time":"2015-01-13T00:00:00Z","timestamp":1421107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Centre (NCN) SONATA 1","award":["2011\/01\/D\/ST6\/07164, 2011--2015"],"award-info":[{"award-number":["2011\/01\/D\/ST6\/07164, 2011--2015"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,1,13]]},"abstract":"<jats:p>\n            In this article, a fully compressed pattern matching problem is studied. The compression is represented by straight-line programs (SLPs)\u2014that is, context-free grammars generating exactly one string; the term\n            <jats:italic>fully<\/jats:italic>\n            means that both the pattern\n            <jats:italic>and<\/jats:italic>\n            the text are given in the compressed form. The problem is approached using a recently developed technique of local recompression: the SLPs are refactored so that substrings of the pattern and text are encoded in both SLPs in the same way. To this end, the SLPs are locally decompressed and then recompressed in a uniform way.\n          <\/jats:p>\n          <jats:p>\n            This technique yields an\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            ) log\n            <jats:italic>M<\/jats:italic>\n            ) algorithm for compressed pattern matching, assuming that\n            <jats:italic>M<\/jats:italic>\n            fits in\n            <jats:italic>O<\/jats:italic>\n            (1) machine words, where\n            <jats:italic>n<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            ) is the size of the compressed representation of the text (pattern, respectively), and\n            <jats:italic>M<\/jats:italic>\n            is the size of the decompressed pattern. If only\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>n<\/jats:italic>\n            fits in\n            <jats:italic>O<\/jats:italic>\n            (1) machine words, the running time increases to\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            ) log\n            <jats:italic>M<\/jats:italic>\n            log (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            )). The previous best algorithm due to Lifshits has\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\n              n\n              <jats:sup>2<\/jats:sup>\n              m\n            <\/jats:italic>\n            ) running time.\n          <\/jats:p>","DOI":"10.1145\/2631920","type":"journal-article","created":{"date-parts":[[2015,1,16]],"date-time":"2015-01-16T14:29:58Z","timestamp":1421418598000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Faster Fully Compressed Pattern Matching by Recompression"],"prefix":"10.1145","volume":"11","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[{"name":"Max Planck Institute f\u00fcr Informatik and Institute of Computer Science, University of Wroc\u0142aw, Wroc\u0142aw, Poland"}]}],"member":"320","published-online":{"date-parts":[[2015,1,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of SODA. 819--828","author":"Alstrup Stephen","year":"2000"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_2_1_3_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithm Theory\u2014SWAT '96","author":"G\u0105sieniec Leszek"},{"key":"e_1_2_1_4_1","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Pattern Matching","author":"G\u0105sieniec Leszek"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/789086.789703"},{"key":"e_1_2_1_6_1","unstructured":"Pawe\u0142 Gawrychowski. 2011a. Personal communication.  Pawe\u0142 Gawrychowski. 2011a. Personal communication."},{"key":"e_1_2_1_7_1","volume-title":"Algorithms\u2014ESA","author":"Gawrychowski Pawe\u0142","year":"2011"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31265-6_19"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of STACS. Leibniz International Proceedings in Informatics","volume":"14","author":"Gawrychowski Pawe\u0142","year":"2012"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483705"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/829519.830821"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9443-6"},{"key":"e_1_2_1_13_1","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Pattern Matching","author":"Je\u017c Artur"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_30"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of STACS. Leibniz International Proceedings in Informatics","volume":"20","author":"Je\u017c Artur","year":"2013"},{"key":"e_1_2_1_16_1","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages, and Programming","author":"Je\u017c Artur"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of STACS. Leibniz International Proceedings in Informatics","volume":"25","author":"Je\u017c Artur","year":"2014"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34109-0_34"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Pattern Matching","author":"Karpi\u0144ski Marek"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Data Compression Conference. IEEE","author":"Jesper Larsson N.","year":"1999"},{"key":"e_1_2_1_21_1","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Pattern Matching","author":"Lifshits Yury"},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Computer Science","volume-title":"Computer Science\u2014Theory and Applications","author":"Lohrey Markus"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02522825"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.   Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Pattern Matching","author":"Miyazaki Masamichi"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622776.1622780"},{"key":"e_1_2_1_27_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms\u2014ESA '94","author":"Plandowski Wojciech"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Wojciech Plandowski and Wojciech Rytter. 1999. Complexity of language recognition problems for compressed words. In Jewels Are Forever Juhani Karhum\u00e4ki Hermann A. Maurer Gheorghe Paun and Grzegorz Rozenberg (Eds.). Springer 262--272.   Wojciech Plandowski and Wojciech Rytter. 1999. Complexity of language recognition problems for compressed words. In Jewels Are Forever Juhani Karhum\u00e4ki Hermann A. Maurer Gheorghe Paun and Grzegorz Rozenberg (Eds.). Springer 262--272.","DOI":"10.1007\/978-3-642-60207-8_23"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00777-6"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.016"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2631920","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2631920","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:13Z","timestamp":1750231153000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2631920"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,13]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1,13]]}},"alternative-id":["10.1145\/2631920"],"URL":"https:\/\/doi.org\/10.1145\/2631920","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,13]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}