{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:23:23Z","timestamp":1772119403686,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T00:00:00Z","timestamp":1693353600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T00:00:00Z","timestamp":1693353600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20J11983"],"award-info":[{"award-number":["JP20J11983"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20J21147"],"award-info":[{"award-number":["JP20J21147"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,3]]},"DOI":"10.1007\/s00453-023-01170-8","type":"journal-article","created":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T10:02:06Z","timestamp":1693389726000},"page":"852-873","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Data Structures for Computing Unique Palindromes in Static and Non-Static Strings"],"prefix":"10.1007","volume":"86","author":[{"given":"Takuya","family":"Mieno","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mitsuru","family":"Funakoshi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,30]]},"reference":[{"issue":"7","key":"1170_CR1","doi-asserted-by":"publisher","first-page":"2088","DOI":"10.1007\/s00453-022-00955-7","volume":"84","author":"P Abedin","year":"2022","unstructured":"Abedin, P., Hooshmand, S., Ganguly, A., et al.: The heaviest induced ancestors problem: better data structures and applications. Algorithmica 84(7), 2088\u20132105 (2022). https:\/\/doi.org\/10.1007\/s00453-022-00955-7","journal-title":"Algorithmica"},{"key":"1170_CR2","doi-asserted-by":"publisher","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T. Marked ancestor problems. In: 39th Annual Symposium on Foundations of Computer Science, FOCS \u201998, November 8-11, 1998, Palo Alto, California, USA. IEEE Computer Society, 534\u2013544, (1998) https:\/\/doi.org\/10.1109\/SFCS.1998.743504","DOI":"10.1109\/SFCS.1998.743504"},{"key":"1170_CR3","unstructured":"Amir, A., Boneh, I.: Dynamic palindrome detection. (2019) CoRR abs\/1906.09732. arxiv:1906.09732"},{"key":"1170_CR4","doi-asserted-by":"publisher","unstructured":"Amir, A., Charalampopoulos, P., Iliopoulos, C.S., et al.: Longest common factor after one edit operation. In: Fici G, Sciortino M, Venturini R (eds) String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings, Lecture Notes in Computer Science, vol 10508. Springer, 14\u201326, (2017) https:\/\/doi.org\/10.1007\/978-3-319-67428-5_2","DOI":"10.1007\/978-3-319-67428-5_2"},{"key":"1170_CR5","doi-asserted-by":"publisher","unstructured":"Amir, A., Boneh, I., Charalampopoulos, P., et al.: Repetition detection in a dynamic string. In: Bender MA, Svensson O, Herman G (eds) 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich\/Garching, Germany, LIPIcs, vol 144. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 5:1\u20135:18, (2019) https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.5","DOI":"10.4230\/LIPIcs.ESA.2019.5"},{"issue":"12","key":"1170_CR6","doi-asserted-by":"publisher","first-page":"3707","DOI":"10.1007\/s00453-020-00744-0","volume":"82","author":"A Amir","year":"2020","unstructured":"Amir, A., Charalampopoulos, P., Pissis, S.P., et al.: Dynamic and internal longest common substring. Algorithmica 82(12), 3707\u20133743 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00744-0","journal-title":"Algorithmica"},{"issue":"1 &2","key":"1170_CR7","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(1 &2), 163\u2013173 (1995). https:\/\/doi.org\/10.1016\/0304-3975(94)00083-U","journal-title":"Theor. Comput. Sci."},{"key":"1170_CR8","doi-asserted-by":"publisher","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: Path minima queries in dynamic weighted trees. In: Dehne F, Iacono J, Sack J (eds) Algorithms and Data Structures - 12th International Symposium, WADS 2011, New York, USA, Aug 15-17, 2011. Proceedings, Lecture Notes in Computer Science, vol 6844. Springer, 290\u2013301, (2011) https:\/\/doi.org\/10.1007\/978-3-642-22300-6_25","DOI":"10.1007\/978-3-642-22300-6_25"},{"key":"1170_CR9","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Gawrychowski, P., Pokorski, K.: Dynamic longest common substring in polylogarithmic time. In: Czumaj A, Dawar A, Merelli E (eds) 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, Jul 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference), LIPIcs, vol 168. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 27:1\u201327:19, (2020) https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.27","DOI":"10.4230\/LIPIcs.ICALP.2020.27"},{"key":"1170_CR10","unstructured":"Clark, D.: Compact Pat Trees. PhD thesis, University of Waterloo (1997)"},{"issue":"4","key":"1170_CR11","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1109\/TCOM.1984.1096090","volume":"32","author":"JG Cleary","year":"1984","unstructured":"Cleary, J.G., Witten, I.H.: Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. 32(4), 396\u2013402 (1984). https:\/\/doi.org\/10.1109\/TCOM.1984.1096090","journal-title":"IEEE Trans. Commun."},{"key":"1170_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2019.104461","author":"M Crochemore","year":"2020","unstructured":"Crochemore, M., H\u00e9liou, A., Kucherov, G., et al.: Absent words in a sliding window with applications. Inf. Comput. (2020). https:\/\/doi.org\/10.1016\/j.ic.2019.104461","journal-title":"Inf. Comput."},{"issue":"3","key":"1170_CR13","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"Boas P van Emde","year":"1977","unstructured":"van Emde, Boas P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6(3), 80\u201382 (1977). https:\/\/doi.org\/10.1016\/0020-0190(77)90031-X","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"1170_CR14","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/63334.63341","volume":"32","author":"ER Fiala","year":"1989","unstructured":"Fiala, E.R., Greene, D.H.: Data compression with finite windows. Commun. ACM 32(4), 490\u2013505 (1989). https:\/\/doi.org\/10.1145\/63334.63341","journal-title":"Commun. ACM"},{"issue":"1","key":"1170_CR15","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","volume":"16","author":"NJ Fine","year":"1965","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Am. Math. Soc. 16(1), 109\u2013114 (1965). https:\/\/doi.org\/10.1090\/S0002-9939-1965-0174934-9","journal-title":"Proc. Am. Math. Soc."},{"issue":"2","key":"1170_CR16","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). https:\/\/doi.org\/10.1137\/090779759","journal-title":"SIAM J. Comput."},{"key":"1170_CR17","doi-asserted-by":"publisher","unstructured":"Funakoshi, M., Mieno, T.: Minimal unique palindromic substrings after single-character substitution. In: Lecroq T, Touzet H (eds) String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, Lille, France, October 4-6, 2021, Proceedings, Lecture Notes in Computer Science, vol 12944. Springer, 33\u201346, (2021) https:\/\/doi.org\/10.1007\/978-3-030-86692-1_4","DOI":"10.1007\/978-3-030-86692-1_4"},{"key":"1170_CR18","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.tcs.2021.01.014","volume":"859","author":"M Funakoshi","year":"2021","unstructured":"Funakoshi, M., Nakashima, Y., Inenaga, S., et al.: Computing longest palindromic substring after single-character or block-wise edits. Theor. Comput. Sci. 859, 116\u2013133 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.01.014","journal-title":"Theor. Comput. Sci."},{"key":"1170_CR19","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-61422-2_148","volume-title":"Algorithm theory \u2013 SWAT\u201996","author":"L Gasieniec","year":"1996","unstructured":"Gasieniec, L., Karpinski, M., Plandowski, W., et al.: Efficient algorithms for Lempel-Ziv encoding. In: Karlsson, R., Lingas, A. (eds.) Algorithm theory \u2013 SWAT\u201996, pp. 392\u2013403. Springer, Berlin Heidelberg (1996)"},{"key":"1170_CR20","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Karczmarz, A., Kociumaka, T., et al.: Optimal dynamic strings. In: Czumaj A (ed) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018. SIAM, 1509\u20131528, (2018) https:\/\/doi.org\/10.1137\/1.9781611975031.99","DOI":"10.1137\/1.9781611975031.99"},{"issue":"9","key":"1170_CR21","doi-asserted-by":"publisher","first-page":"3630","DOI":"10.1007\/s00453-019-00591-8","volume":"81","author":"P Gawrychowski","year":"2019","unstructured":"Gawrychowski, P., Merkurev, O., Shur, A.M., et al.: Tight tradeoffs for real-time approximation of longest palindromes in streams. Algorithmica 81(9), 3630\u20133654 (2019). https:\/\/doi.org\/10.1007\/s00453-019-00591-8","journal-title":"Algorithmica"},{"key":"1170_CR22","doi-asserted-by":"publisher","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. Cambridge University Press (1997). https:\/\/doi.org\/10.1017\/cbo9780511574931","DOI":"10.1017\/cbo9780511574931"},{"key":"1170_CR23","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jda.2018.11.009","volume":"52\u201353","author":"H Inoue","year":"2018","unstructured":"Inoue, H., Nakashima, Y., Mieno, T., et al.: Algorithms and combinatorial properties on shortest unique palindromic substrings. J. Dis. Algorithms 52\u201353, 122\u2013132 (2018). https:\/\/doi.org\/10.1016\/j.jda.2018.11.009","journal-title":"J. Dis. Algorithms"},{"key":"1170_CR24","doi-asserted-by":"publisher","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 Oct\u2013 1 Nov 1989. IEEE Computer Society, 549\u2013554, (1989) https:\/\/doi.org\/10.1109\/SFCS.1989.63533","DOI":"10.1109\/SFCS.1989.63533"},{"key":"1170_CR25","doi-asserted-by":"publisher","unstructured":"Kempa, D., Kociumaka, T.: Dynamic suffix array with polylogarithmic queries and updates. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, New York, USA, STOC 2022, 1657-1670, (2022) https:\/\/doi.org\/10.1145\/3519935.3520061","DOI":"10.1145\/3519935.3520061"},{"issue":"11","key":"1170_CR26","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1111\/j.1349-7006.1992.tb02734.x","volume":"83","author":"E Kuramoto","year":"1992","unstructured":"Kuramoto, E., Yano, O., Kimura, Y., et al.: Oligonucleotide sequences required for natural killer cell activation. Jpn. J. Cancer Res. 83(11), 1128\u20131131 (1992). https:\/\/doi.org\/10.1111\/j.1349-7006.1992.tb02734.x","journal-title":"Jpn. J. Cancer Res."},{"key":"1170_CR27","doi-asserted-by":"publisher","unstructured":"Larsson, N.J.: Extended application of suffix trees to data compression. In: Storer JA, Cohn M (eds) Proceedings of the 6th Data Compression Conference (DCC \u201996), Snowbird, Utah, USA, March 31 - April 3, 1996. IEEE Computer Society, 190\u2013199, (1996) https:\/\/doi.org\/10.1109\/DCC.1996.488324","DOI":"10.1109\/DCC.1996.488324"},{"issue":"3","key":"1170_CR28","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1145\/321892.321896","volume":"22","author":"GK Manacher","year":"1975","unstructured":"Manacher, G.K.: A new linear-time on-line algorithm for finding the smallest initial palindrome of a string. J. ACM 22(3), 346\u2013351 (1975). https:\/\/doi.org\/10.1145\/321892.321896","journal-title":"J. ACM"},{"issue":"8\u201310","key":"1170_CR29","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.tcs.2008.12.016","volume":"410","author":"W Matsubara","year":"2009","unstructured":"Matsubara, W., Inenaga, S., Ishino, A., et al.: Efficient algorithms to compute compressed longest common substrings and compressed palindromes. Theor. Comput. Sci. 410(8\u201310), 900\u2013913 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2008.12.016","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1170_CR30","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1007\/s00453-021-00864-1","volume":"84","author":"T Mieno","year":"2022","unstructured":"Mieno, T., Fujishige, Y., Nakashima, Y., et al.: Computing minimal unique substrings for a sliding window. Algorithmica 84(3), 670\u2013693 (2022). https:\/\/doi.org\/10.1007\/s00453-021-00864-1","journal-title":"Algorithmica"},{"key":"1170_CR31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2021.106174","volume":"173","author":"T Mieno","year":"2022","unstructured":"Mieno, T., Watanabe, K., Nakashima, Y., et al.: Palindromic trees for a sliding window and its applications. Inf. Process. Lett. 173, 106174 (2022). https:\/\/doi.org\/10.1016\/j.ipl.2021.106174","journal-title":"Inf. Process. Lett."},{"key":"1170_CR32","first-page":"41","volume":"2005","author":"M Senft","year":"2005","unstructured":"Senft, M.: Suffix tree for a sliding window: an overview. WDS 2005, 41\u201346 (2005)","journal-title":"WDS"},{"key":"1170_CR33","doi-asserted-by":"publisher","unstructured":"Tsuruta, K., Inenaga, S., Bannai, H., et al.: Shortest unique substrings queries in optimal time. In: SOFSEM 2014: Theory and Practice of Computer Science - 40th International Conference on Current Trends in Theory and Practice of Computer Science, Lecture Notes in Computer Science, vol 8327. Springer, 503\u2013513, (2014)https:\/\/doi.org\/10.1007\/978-3-319-04298-5_44","DOI":"10.1007\/978-3-319-04298-5_44"},{"issue":"3","key":"1170_CR34","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249\u2013260 (1995). https:\/\/doi.org\/10.1007\/BF01206331","journal-title":"Algorithmica"},{"key":"1170_CR35","doi-asserted-by":"publisher","unstructured":"Urabe, Y., Nakashima, Y., Inenaga, S., et al.: Longest Lyndon substring after edit. In: Navarro G, Sankoff D, Zhu B (eds) Annual Symposium on Combinatorial Pattern Matching, CPM 2018, July 2-4, 2018 - Qingdao, China, LIPIcs, vol 105. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1\u201319:10, (2018) https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2018.19","DOI":"10.4230\/LIPIcs.CPM.2018.19"},{"issue":"7","key":"1170_CR36","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1007\/s00224-020-09980-x","volume":"64","author":"K Watanabe","year":"2020","unstructured":"Watanabe, K., Nakashima, Y., Inenaga, S., et al.: Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings. Theor. Comput. Syst. 64(7), 1273\u20131291 (2020). https:\/\/doi.org\/10.1007\/s00224-020-09980-x","journal-title":"Theor. Comput. Syst."},{"issue":"12","key":"1170_CR37","doi-asserted-by":"publisher","first-page":"4072","DOI":"10.4049\/jimmunol.148.12.4072","volume":"148","author":"S Yamamoto","year":"1992","unstructured":"Yamamoto, S., Yamamoto, T., Kataoka, T., et al.: Unique palindromic sequences in synthetic oligonucleotides are required to induce IFN natural killer activity. J. Immunol. 148(12), 4072\u20134076 (1992)","journal-title":"J. Immunol."},{"issue":"3","key":"1170_CR38","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theor. 23(3), 337\u2013343 (1977). https:\/\/doi.org\/10.1109\/TIT.1977.1055714","journal-title":"IEEE Trans. Inf. Theor."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01170-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01170-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01170-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T11:10:37Z","timestamp":1710155437000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01170-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,30]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["1170"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01170-8","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2122747\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,30]]},"assertion":[{"value":"1 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflicts of interest associated with this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}