{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:58:16Z","timestamp":1742932696704,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031270505"},{"type":"electronic","value":"9783031270512"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-27051-2_12","type":"book-chapter","created":{"date-parts":[[2023,3,13]],"date-time":"2023-03-13T00:03:35Z","timestamp":1678665815000},"page":"127-138","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Internal Longest Palindrome Queries in\u00a0Optimal Time"],"prefix":"10.1007","author":[{"given":"Kazuki","family":"Mitani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takuya","family":"Mieno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhisa","family":"Seto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takashi","family":"Horiyama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,13]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2020.04.009","volume":"822","author":"P Abedin","year":"2020","unstructured":"Abedin, P., et al.: A linear-space data structure for range-LCP queries in poly-logarithmic time. Theor. Comput. Sci. 822, 15\u201322 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Abedin, P., Ganguly, A., Pissis, S.P., Thankachan, S.V.: Efficient data structures for range shortest unique substring queries. Algorithms 13(11), 1\u20139 (2020)","DOI":"10.3390\/a13110276"},{"key":"12_CR3","unstructured":"Agarwal, P.K.: Range Searching. In: Handbook of Discrete and Computational Geometry, pp. 1057\u20131092. Chapman and Hall\/CRC, Boca Raton (2017)"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, p. 198. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892088"},{"issue":"7","key":"12_CR5","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1016\/j.jcss.2014.02.010","volume":"80","author":"A Amir","year":"2014","unstructured":"Amir, A., Apostolico, A., Landau, G.M., Levy, A., Lewenstein, M., Porat, E.: Range LCP. J. Comput. Syst. Sci. 80(7), 1245\u20131253 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR6","unstructured":"Amir, A., Boneh, I.: Dynamic palindrome detection. arXiv preprint arXiv:1906.09732 (2019)"},{"issue":"12","key":"12_CR7","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., Radoszewski, J.: Dynamic and internal longest common substring. Algorithmica 82(12), 3707\u20133743 (2020)","journal-title":"Algorithmica"},{"issue":"2","key":"12_CR8","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/1240233.1240242","volume":"3","author":"A Amir","year":"2007","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Sokol, D.: Dynamic text and static pattern matching. ACM Trans. Algorithms 3(2), 19 (2007)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"12_CR9","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), 163\u2013173 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.tcs.2015.08.023","volume":"638","author":"M Babenko","year":"2016","unstructured":"Babenko, M., Gawrychowski, P., Kociumaka, T., Kolesnichenko, I., Starikovskaya, T.: Computing minimal and maximal suffixes of a substring. Theor. Comput. Sci. 638, 112\u2013121 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Badkobeh, G., Charalampopoulos, P., Kosolobov, D., Pissis, S.P.: Internal shortest absent word queries in constant time and linear space. Theor. Comput. Sci. 922, 271\u2013282 (2022)","DOI":"10.1016\/j.tcs.2022.04.029"},{"issue":"4","key":"12_CR12","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L.: Multidimensional divide-and-conquer. Commun. ACM 23(4), 214\u2013229 (1980)","journal-title":"Commun. ACM"},{"key":"12_CR13","unstructured":"Charalampopoulos, P., Gawrychowski, P., Mozes, S., Weimann, O.: An almost optimal edit distance oracle. In: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"7","key":"12_CR14","doi-asserted-by":"publisher","first-page":"2142","DOI":"10.1007\/s00453-021-00821-y","volume":"83","author":"P Charalampopoulos","year":"2021","unstructured":"Charalampopoulos, P., Kociumaka, T., Mohamed, M., Radoszewski, J., Rytter, W., Wale\u0144, T.: Internal dictionary matching. Algorithmica 83(7), 2142\u20132169 (2021)","journal-title":"Algorithmica"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Charalampopoulos, P., Kociumaka, T., Wellnitz, P.: Faster approximate pattern matching: a unified approach. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 978\u2013989. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00095"},{"issue":"1\u20132","key":"12_CR16","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/S0304-3975(99)00320-5","volume":"255","author":"X Droubay","year":"2001","unstructured":"Droubay, X., Justin, J., Pirillo, G.: Episturmian words and some constructions of de Luca and Rauzy. Theor. Comput. Sci. 255(1\u20132), 539\u2013553 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"12_CR17","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":"12_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., Bannai, H., Takeda, M.: Computing longest palindromic substring after single-character or block-wise edits. Theor. Comput. Sci. 859, 116\u2013133 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR19","unstructured":"Ganardi, M.: Compression by contracting straight-line programs. In: Mutzel, P., Pagh, R., Herman, G. (eds.) 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 204, pp. 45:1\u201345:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"3","key":"12_CR20","first-page":"245","volume":"163","author":"A Ganguly","year":"2018","unstructured":"Ganguly, A., Patil, M., Shah, R., Thankachan, S.V.: A linear space data structure for range LCP queries. Fund. Inform. 163(3), 245\u2013251 (2018)","journal-title":"Fund. Inform."},{"issue":"20","key":"12_CR21","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1016\/j.ipl.2010.07.018","volume":"110","author":"R Groult","year":"2010","unstructured":"Groult, R., Prieur, \u00c9., Richomme, G.: Counting distinct palindromes in a word in linear time. Inf. Process. Lett. 110(20), 908\u2013912 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"12_CR22","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/270563.571472","volume":"28","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on stings, trees, and sequences: computer science and computational biology. ACM SIGACT News 28(4), 41\u201360 (1997)","journal-title":"ACM SIGACT News"},{"key":"12_CR23","unstructured":"Kociumaka, T.: Minimal suffix and rotation of a substring in optimal time. In: 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), vol. 54, pp. 28:1\u201328:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"12_CR24","unstructured":"Kociumaka, T.: Efficient data structures for internal queries in texts. Ph.D. thesis, University of Warsaw (2018)"},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., Wale\u0144, T.: Internal pattern matching queries in a text and applications. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 532\u2013551. SIAM (2014)","DOI":"10.1137\/1.9781611973730.36"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Manacher, G.: A new linear-time \u201con-line\u201d algorithm for finding the smallest initial palindrome of a string. J. ACM (JACM) 22(3), 346\u2013351 (1975)","DOI":"10.1145\/321892.321896"},{"issue":"8\u201310","key":"12_CR27","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., Shinohara, A., Nakamura, T., Hashimoto, K.: Efficient algorithms to compute compressed longest common substrings and compressed palindromes. Theor. Comput. Sci. 410(8\u201310), 900\u2013913 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR28","unstructured":"Matsuda, K., Sadakane, K., Starikovskaya, T., Tateshita, M.: Compressed orthogonal search on suffix arrays with applications to range LCP. In: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 232\u2013240 (2006)","DOI":"10.1145\/1132516.1132551"},{"key":"12_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-319-67428-5_25","volume-title":"String Processing and Information Retrieval","author":"M Rubinchik","year":"2017","unstructured":"Rubinchik, M., Shur, A.M.: Counting palindromes in substrings. In: Fici, G., Sciortino, M., Venturini, R. (eds.) SPIRE 2017. LNCS, vol. 10508, pp. 290\u2013303. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-67428-5_25"},{"key":"12_CR31","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.ejc.2017.07.021","volume":"68","author":"M Rubinchik","year":"2018","unstructured":"Rubinchik, M., Shur, A.M.: Eertree: an efficient data structure for processing palindromes in strings. Eur. J. Comb. 68, 249\u2013265 (2018)","journal-title":"Eur. J. Comb."},{"key":"12_CR32","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.tcs.2018.06.034","volume":"753","author":"Y Sakai","year":"2019","unstructured":"Sakai, Y.: A substring-substring LCS data structure. Theor. Comput. Sci. 753, 16\u201334 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR33","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.tcs.2022.02.004","volume":"911","author":"Y Sakai","year":"2022","unstructured":"Sakai, Y.: A data structure for substring-substring LCS length queries. Theor. Comput. Sci. 911, 41\u201354 (2022)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"12_CR34","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/s11786-007-0033-3","volume":"1","author":"A Tiskin","year":"2008","unstructured":"Tiskin, A.: Semi-local string comparison: algorithmic techniques and applications. Math. Comput. Sci. 1(4), 571\u2013603 (2008)","journal-title":"Math. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-27051-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T06:13:36Z","timestamp":1729059216000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-27051-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031270505","9783031270512"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-27051-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"13 March 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hsinchu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 March 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 March 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.walcom2023.conf.nycu.edu.tw\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"75","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This proceeding includes 2 invited papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}