{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T08:33:55Z","timestamp":1790843635303,"version":"4.1.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T00:00:00Z","timestamp":1559606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T00:00:00Z","timestamp":1559606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Wroclaw"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s00453-019-00591-8","type":"journal-article","created":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T09:05:46Z","timestamp":1559639146000},"page":"3630-3654","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams"],"prefix":"10.1007","volume":"81","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oleg","family":"Merkurev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arseny M.","family":"Shur","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8652-0490","authenticated-orcid":false,"given":"Przemys\u0142aw","family":"Uzna\u0144ski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,6,4]]},"reference":[{"key":"591_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0304-3975(94)00083-U","volume":"141","author":"A Apostolico","year":"1995","unstructured":"Apostolico, A., Breslauer, D., Galil, Z.: Parallel detection of all palindromes in a string. Theor. Comput. Sci. 141, 163\u2013173 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"591_CR2","unstructured":"Berenbrink, P., Erg\u00fcn, F., Mallmann-Trenn, F., Azer, E.S.: Palindrome recognition in the streaming model. In: STACS 2014, LIPIcs, vol.\u00a025, pp. 149\u2013161. SchlossDagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl Publishing, Germany (2014)"},{"key":"591_CR3","doi-asserted-by":"crossref","unstructured":"Breslauer, D., Galil, Z.: Real-time streaming string-matching. In: Combinatorial Pattern Matching. LNCS, vol. 6661, pp. 162\u2013172. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-21458-5_15"},{"key":"591_CR4","doi-asserted-by":"crossref","unstructured":"Clifford, R., Fontaine, A., Porat, E., Sach, B., Starikovskaya, T.A.: Dictionary matching in a stream. In: ESA 2015, LNCS, vol. 9294, pp. 361\u2013372. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_31"},{"key":"591_CR5","doi-asserted-by":"crossref","unstructured":"Clifford, R., Fontaine, A., Porat, E., Sach, B., Starikovskaya, T.A.: The k-mismatch problem revisited. In: SODA 2016, pp. 2039\u20132052. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch142"},{"key":"591_CR6","doi-asserted-by":"crossref","unstructured":"Erg\u00fcn, F., Jowhari, H., Saglam, M.: Periodicity in streams. In: RANDOM 2010, LNCS, vol. 6302, pp. 545\u2013559. Springer (2010)","DOI":"10.1007\/978-3-642-15369-3_41"},{"key":"591_CR7","doi-asserted-by":"crossref","unstructured":"Galil, Z.: Real-time algorithms for string-matching and palindrome recognition. In: Proceedings of 8th annual ACM symposium on theory of computing (STOC\u201976), pp. 161\u2013173. ACM, New York (1976)","DOI":"10.1145\/800113.803644"},{"key":"591_CR8","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1145\/322047.322056","volume":"25","author":"Z Galil","year":"1978","unstructured":"Galil, Z., Seiferas, J.: A linear-time on-line recognition algorithm for \u201cPalstar\u201d. J. ACM 25, 102\u2013111 (1978)","journal-title":"J. ACM"},{"key":"591_CR9","unstructured":"Gawrychowski, P., Manea, F., Nowotka, D.: Testing generalised freeness of words. In: STACS 2014, LIPIcs, vol.\u00a025, pp. 337\u2013349. Dagstuhl Publishing (2014)"},{"key":"591_CR10","unstructured":"Gawrychowski, P., Merkurev, O., Shur, A.M., Uznanski, P.: Tight tradeoffs for real-time approximation of longest palindromes in streams. In: Proceedings CPM 2016, LIPIcs, vol.\u00a054, pp. 18:1\u201318:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"key":"591_CR11","unstructured":"Jalsenius, M., Porat, B., Sach, B.: Parameterized matching in the streaming model. In: STACS 2013, LIPIcs, vol.\u00a020, pp. 400\u2013411. Dagstuhl Publishing (2013)"},{"key":"591_CR12","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R Karp","year":"1987","unstructured":"Karp, R., Rabin, M.: Efficient randomized pattern matching algorithms. IBM J. Res. Dev. 31, 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"591_CR13","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":"591_CR14","unstructured":"Kosolobov, D., Rubinchik, M., Shur, A.M.: Finding distinct subpalindromes online. In: Proceedings of Prague Stringology conference. PSC 2013, pp. 63\u201369. Czech Technical University in Prague (2013)"},{"issue":"3","key":"591_CR15","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1145\/321892.321896","volume":"22","author":"G Manacher","year":"1975","unstructured":"Manacher, G.: A new linear-time on-line algorithm finding the smallest initial palindrome of a string. J. ACM 22(3), 346\u2013351 (1975)","journal-title":"J. ACM"},{"key":"591_CR16","doi-asserted-by":"crossref","unstructured":"Porat, B., Porat, E.: Exact and approximate pattern matching in the streaming model. In: FOCS 2009, pp. 315\u2013323. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.11"},{"key":"591_CR17","doi-asserted-by":"publisher","first-page":"371","DOI":"10.3233\/FI-2016-1366","volume":"145","author":"M Rubinchik","year":"2016","unstructured":"Rubinchik, M., Shur, A.M.: The number of distinct subpalindromes in random words. Fundam. Inform. 145, 371\u2013384 (2016)","journal-title":"Fundam. Inform."},{"key":"591_CR18","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Probabilistic computations: toward a unified measure of complexity (extended abstract). In: FOCS 1977, pp. 222\u2013227. IEEE Computer Society (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00591-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00591-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00591-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,2]],"date-time":"2020-06-02T23:22:51Z","timestamp":1591140171000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00591-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,4]]},"references-count":18,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["591"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00591-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,4]]},"assertion":[{"value":"18 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}