{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T08:34:20Z","timestamp":1790843660245,"version":"4.1.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,8,15]],"date-time":"2017-08-15T00:00:00Z","timestamp":1502755200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"DFG","award":["596676"],"award-info":[{"award-number":["596676"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00224-017-9794-5","type":"journal-article","created":{"date-parts":[[2017,8,15]],"date-time":"2017-08-15T07:27:42Z","timestamp":1502782062000},"page":"162-191","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Tighter Bounds and Optimal Algorithms for All Maximal \u03b1-gapped Repeats and Palindromes"],"prefix":"10.1007","volume":"62","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomohiro","family":"I","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dominik","family":"K\u00f6ppl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florin","family":"Manea","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,8,15]]},"reference":[{"issue":"3","key":"9794_CR1","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1016\/j.jcss.2015.11.007","volume":"82","author":"G Badkobeh","year":"2016","unstructured":"Badkobeh, G., Crochemore, M.: Computing maximal-exponent factors in an overlap-free word. J. Comput. Syst Sci. 82(3), 477\u2013487 (2016)","journal-title":"J. Comput. Syst Sci."},{"key":"9794_CR2","unstructured":"Bannai, H., Tomohiro, I., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The runs theorem. arXiv: 1406.0263 (2014)"},{"key":"9794_CR3","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Lyngs\u00f8, R. B., Pedersen, C. N. S., Stoye, J.: Finding maximal pairs with bounded gap Proc. CPM, volume 1645 of LNCS, pp 134\u2013149 (1999)","DOI":"10.1007\/3-540-48452-3_11"},{"issue":"1","key":"9794_CR4","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0304-3975(91)90073-B","volume":"88","author":"M Crochemore","year":"1991","unstructured":"Crochemore, M., Rytter, W.: Usefulness of the karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays. Theor. Comput. Sci. 88(1), 59\u201382 (1991)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"9794_CR5","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.ipl.2010.12.005","volume":"111","author":"M Crochemore","year":"2011","unstructured":"Crochemore, M., Tischler, G.: Computing longest previous non-overlapping factors. Inf. Process. Lett. 111(6), 291\u2013295 (2011)","journal-title":"Inf. Process. Lett."},{"key":"9794_CR6","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Iliopoulos, C. S., Kubica, M., Rytter, W., Walen, T.: Efficient Algorithms for Two Extensions of LPF table: The Power of Suffix Arrays Proc. SOFSEM, volume 5901 of LNCS, pp 296\u2013307 (2010)","DOI":"10.1007\/978-3-642-11266-9_25"},{"key":"9794_CR7","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Kolpakov, R., Kucherov, G.: Optimal Bounds for Computing \u03b1-Gapped Repeats Proc. LATA, pp 245\u2013255 (2016)","DOI":"10.1007\/978-3-319-30000-9_19"},{"key":"9794_CR8","doi-asserted-by":"crossref","unstructured":"Dumitran, M., Manea, F.: Longest Gapped Repeats and Palindromes Proc. MFCS, volume 9234 of LNCS, pp 205\u2013217 (2015)","DOI":"10.1007\/978-3-662-48057-1_16"},{"issue":"2","key":"9794_CR9","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"key":"9794_CR10","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Manea, F.: Longest \u03b1-Gapped Repeat and Palindrome Proc. FCT, volume 9210 of LNCS, pp 27\u201340 (2015)","DOI":"10.1007\/978-3-319-22177-9_3"},{"key":"9794_CR11","unstructured":"Gawrychowski, P., Manea, F., Mercas, R., Nowotka, D., Tiseanu, C.: Finding Pseudo-repetitions Proc. STACS, volume 20 of LIPIcs, pp 257\u2013268 (2013)"},{"key":"9794_CR12","unstructured":"Gawrychowski, P., Manea, F., Nowotka, D.: Testing Generalised Freeness of Words Proc. STACS, volume 25 of LIPIcs, pp 337\u2013349 (2014)"},{"key":"9794_CR13","unstructured":"Gawrychowski, P., Tomohiro, I., Inenaga, S., K\u00f6ppl, D., Manea, F.: Efficiently finding all maximal \u03b1-gapped repeats Proc. STACS, volume 47 of LIPIcs, pp 39:1\u201339:14 (2016)"},{"key":"9794_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences: computer science and computational biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, Cambridge (1997)"},{"key":"9794_CR15","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53, 918\u2013936 (2006)","journal-title":"J. ACM"},{"key":"9794_CR16","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., Walen, T.: Efficient Data Structures for the Factor Periodicity Problem Proc. SPIRE, volume 7608 of LNCS, pp 284\u2013294 (2012)","DOI":"10.1007\/978-3-642-34109-0_30"},{"key":"9794_CR17","doi-asserted-by":"crossref","unstructured":"Kolpakov, R., Kucherov, G.: Finding Repeats with Fixed Gap Proc. SPIRE, pp 162\u2013168 (2000)","DOI":"10.1109\/SPIRE.2000.878192"},{"issue":"51","key":"9794_CR18","doi-asserted-by":"publisher","first-page":"5365","DOI":"10.1016\/j.tcs.2009.09.013","volume":"410","author":"R Kolpakov","year":"2009","unstructured":"Kolpakov, R., Kucherov, G.: Searching for gapped palindromes. Theor. Comput. Sci. 410(51), 5365\u20135373 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9794_CR19","doi-asserted-by":"crossref","unstructured":"Kolpakov, R., Podolskiy, M., Posypkin, M., Khrapov, N.: Searching of Gapped Repeats and Subrepetitions in a Word Proc. CPM, volume 8486 of LNCS, pp 212\u2013221 (2014)","DOI":"10.1007\/978-3-319-07566-2_22"},{"issue":"3","key":"9794_CR20","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 \u201con-line\u201d algorithm for finding the smallest initial palindrome of a string. J. ACM 22(3), 346\u2013351 (1975)","journal-title":"J. ACM"},{"key":"9794_CR21","doi-asserted-by":"crossref","unstructured":"Ruzic, M.: Making deterministic signatures quickly. ACM Transactions on Algorithms 5 (3) (2009)","DOI":"10.1145\/1541885.1541887"},{"key":"9794_CR22","doi-asserted-by":"crossref","unstructured":"Tanimura, Y., Fujishige, Y., Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: A faster algorithm for computing maximal \u03b1-gapped repeats in a string Proc. SPIRE, volume 9309 of LNCS, pp 124\u2013136 (2015)","DOI":"10.1007\/978-3-319-23826-5_13"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9794-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9794-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9794-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T22:52:49Z","timestamp":1750805569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9794-5"}},"subtitle":["Finding All Maximal \u03b1-gapped Repeats and Palindromes in Optimal Worst Case Time on Integer Alphabets"],"short-title":[],"issued":{"date-parts":[[2017,8,15]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9794"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9794-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,15]]},"assertion":[{"value":"15 August 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}