{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:02Z","timestamp":1740109322466,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,11,3]],"date-time":"2021-11-03T00:00:00Z","timestamp":1635897600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,3]],"date-time":"2021-11-03T00:00:00Z","timestamp":1635897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100012190","name":"Ministry of Science and Higher Education of the Russian Federation","doi-asserted-by":"crossref","award":["Ural Mathematical Center Project No. 075-02-2021-1387"],"award-info":[{"award-number":["Ural Mathematical Center Project No. 075-02-2021-1387"]}],"id":[{"id":"10.13039\/501100012190","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s00453-021-00883-y","type":"journal-article","created":{"date-parts":[[2021,11,3]],"date-time":"2021-11-03T07:03:44Z","timestamp":1635923024000},"page":"742-756","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing The Maximum Exponent in a Stream"],"prefix":"10.1007","volume":"84","author":[{"given":"Oleg","family":"Merkurev","sequence":"first","affiliation":[]},{"given":"Arseny M.","family":"Shur","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,3]]},"reference":[{"issue":"3","key":"883_CR1","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1236457.1236460","volume":"54","author":"A Andersson","year":"2007","unstructured":"Andersson, A., Thorup, M.: Dynamic ordered sets with exponential search trees. J. ACM 54(3), 13 (2007)","journal-title":"J. ACM"},{"key":"883_CR2","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: De-amortized cuckoo hashing: Provable worst-case performance and experimental results. In: 36th International Colloquium Automata, Languages and Programming, ICALP 2009, Lecture Notes in Computer Science, vol. 5555, pp. 107\u2013118. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"883_CR3","doi-asserted-by":"crossref","unstructured":"Badkobeh, G., Crochemore, M., Toopsuwan, C.: Computing the maximal-exponent repeats of an overlap-free string in linear time. In: Proceedings 19th International Symposium String Processing and Information Retrieval, SPIRE 2012, Lecture Notes in Computer Science, vol. 7608, pp. 61\u201372. Springer (2012)","DOI":"10.1007\/978-3-642-34109-0_8"},{"key":"883_CR4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(88)90009-6","volume":"23","author":"FJ Brandenburg","year":"1983","unstructured":"Brandenburg, F.J.: Uniformly growing $$k$$-th power-free homomorphisms. Theoret. Comput. Sci. 23, 69\u201382 (1983)","journal-title":"Theoret. Comput. Sci."},{"key":"883_CR5","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-642-21458-5_15","volume-title":"Combinatorial pattern matching","author":"D Breslauer","year":"2011","unstructured":"Breslauer, D., Galil, Z.: Real-time streaming string-matching. In: Combinatorial pattern matching. LNCS, vol. 6661, pp. 162\u2013172. Springer, Berlin (2011)"},{"key":"883_CR6","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Iliopoulos, C.S., Kociumaka, T., Kundu, R., Pissis, S.P., Radoszewski, J., Rytter, W., Walen, T.: Near-optimal computation of runs over general alphabet via non-crossing LCE queries. In: 23rd International Symposium String Processing and Information Retrieval, SPIRE 2016, Lecture Notes in Computer Science, vol. 9954, pp. 22\u201334 (2016)","DOI":"10.1007\/978-3-319-46049-9_3"},{"key":"883_CR7","doi-asserted-by":"publisher","first-page":"104434","DOI":"10.1016\/j.ic.2019.104434","volume":"268","author":"M Crochemore","year":"2019","unstructured":"Crochemore, M., Kolpakov, R., Kucherov, G.: Optimal bounds for computing $$\\alpha $$-gapped repeats. Inf. Comput. 268, 104434 (2019)","journal-title":"Inf. Comput."},{"key":"883_CR8","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., auf der Heide, F.M.: Dynamic hashing in real time. In: Informatik, pp. 95\u2013119. Springer (1992)","DOI":"10.1007\/978-3-322-95233-2_7"},{"issue":"3","key":"883_CR9","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"ML Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424\u2013436 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"883_CR10","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"883_CR11","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J., Pratt, V.: Fast pattern matching in strings. SIAM J. Comput. 6, 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"883_CR12","doi-asserted-by":"crossref","unstructured":"Kolpakov, R., Podolskiy, M., Posypkin, M., Khrapov, N.: Searching of gapped repeats and subrepetitions in a word. In: Proceedings 25th Annual Symposium Combinatorial Pattern Matching, CPM 2014, Moscow, Russia, June 16-18, 2014, Lecture Notes in Computer Science, vol. 8486, pp. 212\u2013221. Springer (2014)","DOI":"10.1007\/978-3-319-07566-2_22"},{"key":"883_CR13","first-page":"596","volume":"99","author":"RM Kolpakov","year":"1999","unstructured":"Kolpakov, R.M., Kucherov, G.: Finding maximal repetitions in a word in linear time. IEEE Comput. Soc. 99, 596\u2013604 (1999)","journal-title":"IEEE Comput. Soc."},{"key":"883_CR14","unstructured":"Merkurev, O., Shur, A.M.: Searching long repeats in streams. In: 30th Annual Symposium on Combinatorial Pattern Matching CPM 2019, LIPIcs, vol. 128, pp. 1\u201314 (2019)"},{"key":"883_CR15","doi-asserted-by":"crossref","unstructured":"Merkurev, O., Shur, A.M.: Searching runs in streams. In: Proceedings 26th International Symposium String Processing and Information Retrieval, SPIRE 2019, Lecture Notes in Computer Science, vol. 11811, pp. 203\u2013220. Springer (2019)","DOI":"10.1007\/978-3-030-32686-9_15"},{"key":"883_CR16","doi-asserted-by":"crossref","unstructured":"Porat, B., Porat, E.: Exact and approximate pattern matching in the streaming model. In: 50th Annual IEEE Symposium on Foundations of Computer Science, 2009. FOCS\u201909. pp. 315\u2013323. IEEE (2009)","DOI":"10.1109\/FOCS.2009.11"},{"key":"883_CR17","first-page":"350","volume-title":"Growth of power-free languages over large alphabets","author":"AM Shur","year":"2010","unstructured":"Shur, A.M.: Growth of power-free languages over large alphabets, vol. 6072, pp. 350\u2013361. Springer, Berlin (2010)"},{"key":"883_CR18","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.cosrev.2012.09.001","volume":"6","author":"AM Shur","year":"2012","unstructured":"Shur, A.M.: Growth properties of power-free languages. Comput. Sci. Rev. 6, 187\u2013208 (2012)","journal-title":"Comput. Sci. Rev."},{"key":"883_CR19","unstructured":"Thue, A.: \u00dcber unendliche Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 7, 1\u201322 (1906)"},{"key":"883_CR20","unstructured":"Thue, A.: \u00dcber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1, 1\u201367 (1912)"},{"key":"883_CR21","doi-asserted-by":"crossref","unstructured":"Yao, A.: Probabilistic computations: toward a unified measure of complexity. In: Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00883-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00883-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00883-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T09:05:41Z","timestamp":1647335141000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00883-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,3]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["883"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00883-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,11,3]]},"assertion":[{"value":"3 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}