{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:19Z","timestamp":1770921379044,"version":"3.50.1"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-17801-5_10","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:52:52Z","timestamp":1770918772000},"page":"128-143","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Asymptotically Optimal Representation of\u00a0Palindromic Structure"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-4783-2537","authenticated-orcid":false,"given":"Michael","family":"Itzhaki","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","unstructured":"Amir, A., Itzhaki, M.: Reconstructing general matching graphs. In: Inenaga, S., Puglisi, S.J. (eds.) 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0296, pp. 2:1\u20132:15 (2024). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2024.2","DOI":"10.4230\/LIPIcs.CPM.2024.2"},{"key":"10_CR2","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Pissis, S.P., Radoszewski, J.: Longest palindromic substring in sublinear time. In: Bannai, H., Holub, J. (eds.) 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). LIPIcs, vol.\u00a0223, pp. 20:1\u201320:9. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2022.20","DOI":"10.4230\/LIPIcs.CPM.2022.20"},{"key":"10_CR3","unstructured":"Clark, D.: Compact PAT Trees. Ph.D. thesis, University of Waterloo, Waterloo, Canada (1996). https:\/\/dl.acm.org\/doi\/10.5555\/287799"},{"key":"10_CR4","doi-asserted-by":"publisher","unstructured":"Dvo\u0159\u00e1kov\u00e1, L., Kruml, S., Ryz\u00e1k, D.: Antipalindromic numbers. Acta Polytechnica 61(3), 428\u2013434 (2021). https:\/\/doi.org\/10.14311\/AP.2021.61.0428","DOI":"10.14311\/AP.2021.61.0428"},{"key":"10_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-540-72845-0_16","volume-title":"Experimental Algorithms","author":"K Fredriksson","year":"2007","unstructured":"Fredriksson, K., Nikitin, F.: Simple compression code supporting random access and fast string matching. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 203\u2013216. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72845-0_16"},{"issue":"2","key":"10_CR6","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/j.bbrc.2003.09.014","volume":"310","author":"A Fuglsang","year":"2003","unstructured":"Fuglsang, A.: Distribution of potential type II restriction sites (palindromes) in prokaryotes. Biochem. Biophys. Res. Commun. 310(2), 280\u2013285 (2003). https:\/\/doi.org\/10.1016\/j.bbrc.2003.09.014","journal-title":"Biochem. Biophys. Res. Commun."},{"key":"10_CR7","doi-asserted-by":"publisher","unstructured":"Galil, Z., Seiferas, J.: Recognizing certain repetitions and reversals within strings. In: Proceedings of the 17th Annual Symposium on Foundations of Computer Science (FOCS 1976), pp. 236\u2013252. IEEE Computer Society (1976). https:\/\/doi.org\/10.1109\/SFCS.1976.25","DOI":"10.1109\/SFCS.1976.25"},{"key":"10_CR8","doi-asserted-by":"publisher","unstructured":"Ganardi, M., Gawrychowski, P.: Pattern matching on grammar-compressed strings in linear time. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pp. 2833\u20132846. Society for Industrial and Applied Mathematics (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.110","DOI":"10.1137\/1.9781611977073.110"},{"key":"10_CR9","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Gourdel, G., Starikovskaya, T., Steiner, T.A.: Compressed consecutive pattern matching. In: Proceedings of the 2024 Data Compression Conference (DCC 2024), pp. 163\u2013172. IEEE (2024). https:\/\/doi.org\/10.1109\/DCC58796.2024.00024","DOI":"10.1109\/DCC58796.2024.00024"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"2430","DOI":"10.1093\/nar\/25.12.2430","volume":"25","author":"MS Gelfand","year":"1997","unstructured":"Gelfand, M.S., Koonin, E.V.: Avoidance of palindromic words in bacterial and archaeal genomes: a close connection with restriction enzymes. Nucleic Acids Res. 25, 2430\u20132439 (1997). https:\/\/doi.org\/10.1093\/nar\/25.12.2430","journal-title":"Nucleic Acids Res."},{"key":"10_CR11","doi-asserted-by":"publisher","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 841\u2013850. Society for Industrial and Applied Mathematics (2003). https:\/\/doi.org\/10.5555\/644108.644250","DOI":"10.5555\/644108.644250"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","volume":"40","author":"DA Huffman","year":"1952","unstructured":"Huffman, D.A.: A method for the construction of minimum-redundancy codes. Proc. IRE 40, 1098\u20131101 (1952). https:\/\/doi.org\/10.1109\/JRPROC.1952.273898","journal-title":"Proc. IRE"},{"key":"10_CR13","doi-asserted-by":"publisher","unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Counting and verifying maximal palindromes. In: Chavez, E., Lonardi, S. (eds.) String Processing and Information Retrieval. LNCS, vol.\u00a06393, pp. 135\u2013146. Springer, Heidelberg (2010).https:\/\/doi.org\/10.1007\/978-3-642-16321-0_13","DOI":"10.1007\/978-3-642-16321-0_13"},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-319-07566-2_16","volume-title":"Combinatorial Pattern Matching","author":"T I","year":"2014","unstructured":"I, T., Sugimoto, S., Inenaga, S., Bannai, H., Takeda, M.: Computing palindromic factorizations and palindromic covers on-line. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 150\u2013161. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07566-2_16"},{"key":"10_CR15","unstructured":"Itzhaki, M.: Asymptotically optimal representation of palindromic structure (2025). https:\/\/arxiv.org\/abs\/2410.09984"},{"key":"10_CR16","doi-asserted-by":"publisher","unstructured":"Itzhaki, M.: Combinatorics of palindromes. In: Je\u017c, A., Otop, J. (eds.) Fundamentals of Computation Theory. LNCS, vol. 16106, pp. 252\u2013266. Springer, Heidelberg (2025). https:\/\/doi.org\/10.1007\/978-3-032-04700-7_19","DOI":"10.1007\/978-3-032-04700-7_19"},{"key":"10_CR17","doi-asserted-by":"publisher","unstructured":"Itzhaki, M.: Palindromes compression and retrieval. In: 2025 Data Compression Conference (DCC), p.\u00a0375 (2025). https:\/\/doi.org\/10.1109\/DCC62719.2025.00062","DOI":"10.1109\/DCC62719.2025.00062"},{"key":"10_CR18","doi-asserted-by":"publisher","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), pp. 549\u2013554. IEEE Computer Society (1989). https:\/\/doi.org\/10.1109\/SFCS.1989.63533","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"2","key":"10_CR19","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BF01182773","volume":"11","author":"J Jeuring","year":"1994","unstructured":"Jeuring, J.: The derivation of on-line algorithms, with an application to finding palindromes. Algorithmica 11(2), 146\u2013184 (1994). https:\/\/doi.org\/10.1007\/BF01182773","journal-title":"Algorithmica"},{"key":"10_CR20","doi-asserted-by":"publisher","unstructured":"Kempa, D., Kociumaka, T.: Breaking the $$\\cal{O}(n)$$-barrier in the construction of compressed suffix arrays and suffix trees. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pp. 5122\u20135202. Society for Industrial and Applied Mathematics (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.ch187","DOI":"10.1137\/1.9781611977554.ch187"},{"key":"10_CR21","doi-asserted-by":"publisher","unstructured":"Kempa, D., Kociumaka, T.: Collapsing the hierarchy of compressed data structures: suffix arrays in optimal compressed space. In: Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023), pp. 1877\u20131886. IEEE Computer Society (2023). https:\/\/doi.org\/10.1109\/FOCS57990.2023.00114","DOI":"10.1109\/FOCS57990.2023.00114"},{"key":"10_CR22","doi-asserted-by":"publisher","unstructured":"Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6, 323\u2013350 (1977). https:\/\/doi.org\/10.1137\/0206024","DOI":"10.1137\/0206024"},{"key":"10_CR23","doi-asserted-by":"publisher","unstructured":"Kosolobov, D., Rubinchik, M., Shur, A.M.: $$\\rm Pal^k$$ is linear recognizable online. In: Italiano, G.F., Margaria-Steffen, T., Pokorn\u00fd, J., Quisquater, J.J., Wattenhofer, R. (eds.) SOFSEM 2015: Theory and Practice of Computer Science. LNCS, vol.\u00a08939, pp. 289\u2013301. Springer, Heidelberg (2015).https:\/\/doi.org\/10.1007\/978-3-662-46078-8_24","DOI":"10.1007\/978-3-662-46078-8_24"},{"key":"10_CR24","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A Lempel","year":"1976","unstructured":"Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Trans. Inf. Theory 22, 75\u201381 (1976). https:\/\/doi.org\/10.1109\/TIT.1976.1055501","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10_CR25","doi-asserted-by":"publisher","unstructured":"Lempel, A., Ziv, J.: Compression of two-dimensional images. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words, NATO ASI Series F, vol.\u00a012, pp. 141\u2013154. Springer, Heidelberg (1985). https:\/\/doi.org\/10.1007\/978-3-642-82456-2_10","DOI":"10.1007\/978-3-642-82456-2_10"},{"key":"10_CR26","doi-asserted-by":"publisher","unstructured":"Lenz, A., Wachter-Zeh, A., Yaakobi, E.: Duplication-correcting codes. Des. Codes Cryptogr. 87(2), 277\u2013298 (2019). https:\/\/doi.org\/10.1007\/s10623-018-0523-0","DOI":"10.1007\/s10623-018-0523-0"},{"key":"10_CR27","doi-asserted-by":"publisher","unstructured":"Lisnic, B., Svetec, I.K., Saric, H., Nikolic, I., Zgaga, Z.: Palindrome content of the yeast Saccharomyces cerevisiae genome. Curr. Genetics 47, 289\u2013297 (2005). https:\/\/doi.org\/10.1007\/s00294-005-0573-5","DOI":"10.1007\/s00294-005-0573-5"},{"key":"10_CR28","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1145\/321892.321896","DOI":"10.1145\/321892.321896"},{"key":"10_CR29","unstructured":"Mieno, T.: Compact representation of maximal palindromes (2025). https:\/\/arxiv.org\/abs\/2508.14384"},{"key":"10_CR30","doi-asserted-by":"publisher","unstructured":"Miller, V.S., Wegman, M.N.: Variations on a theme by Ziv and Lempel. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words, NATO ASI Series F, vol.\u00a012, pp. 131\u2013140. Springer, Heidelberg (1985).https:\/\/doi.org\/10.1007\/978-3-642-82456-2_9","DOI":"10.1007\/978-3-642-82456-2_9"},{"key":"10_CR31","doi-asserted-by":"publisher","unstructured":"Nagashita, S., I, T.: PalFM-index: FM-index for palindrome pattern matching. In: Bulteau, L., Lipt\u00e1k, Z. (eds.) 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). LIPIcs, vol.\u00a0259, pp. 23:1\u201323:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2023.23","DOI":"10.4230\/LIPIcs.CPM.2023.23"},{"key":"10_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-642-31265-6_2","volume-title":"Combinatorial Pattern Matching","author":"G Navarro","year":"2012","unstructured":"Navarro, G.: Wavelet trees for all. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol. 7354, pp. 2\u201326. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31265-6_2"},{"issue":"4","key":"10_CR33","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding $$k$$-ary trees, prefix sums and multisets. ACM Trans. Algor. 3(4), 43 (2007). https:\/\/doi.org\/10.1145\/1290672.1290680","journal-title":"ACM Trans. Algor."},{"key":"10_CR34","doi-asserted-by":"publisher","unstructured":"Rubinchik, M., Shur, A.M.: EERTREE: an efficient data structure for processing palindromes in strings. Eur. J. Comb. 68, 249\u2013265 (2018). https:\/\/doi.org\/10.1016\/j.ejc.2017.07.021","DOI":"10.1016\/j.ejc.2017.07.021"},{"key":"10_CR35","doi-asserted-by":"publisher","unstructured":"Rubinchik, M., Shur, A.M.: Palindromic k-factorization in pure linear time. In: Esparza, J., Kr\u00e1l\u2019, D. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0170, pp. 81:1\u201381:14. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2020). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.81","DOI":"10.4230\/LIPIcs.MFCS.2020.81"},{"issue":"12","key":"10_CR36","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0052250","volume":"7","author":"SK Srivastava","year":"2012","unstructured":"Srivastava, S.K., Robins, H.S.: Palindromic nucleotide analysis in human T cell receptor rearrangements. PLoS ONE 7(12), e52250 (2012). https:\/\/doi.org\/10.1371\/journal.pone.0052250","journal-title":"PLoS ONE"},{"issue":"3","key":"10_CR37","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. Theory 23(3), 337\u2013343 (1977). https:\/\/doi.org\/10.1109\/TIT.1977.1055714","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:52:54Z","timestamp":1770918774000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}