{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T23:37:04Z","timestamp":1743032224403,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031721991"},{"type":"electronic","value":"9783031722004"}],"license":[{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-72200-4_1","type":"book-chapter","created":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:01:50Z","timestamp":1726686110000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Linear Time Reconstruction of Parameterized Strings from Parameterized Suffix and LCP Arrays for Constant-Sized Alphabets"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3939-337X","authenticated-orcid":false,"given":"Amihood","family":"Amir","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9625-7534","authenticated-orcid":false,"given":"Eitan","family":"Kondratovsky","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0008-6692-1693","authenticated-orcid":false,"given":"Shoshana","family":"Marcus","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2478-2636","authenticated-orcid":false,"given":"Dina","family":"Sokol","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.tcs.2020.11.023","volume":"852","author":"A Amir","year":"2021","unstructured":"Amir, A., Kondratovsky, E.: Towards a real time algorithm for parameterized longest common prefix computation. Theoret. Comput. Sci. 852, 132\u2013137 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2020.11.023","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114230","volume":"981","author":"A Amir","year":"2024","unstructured":"Amir, A., Kondratovsky, E., Landau, G.M., Marcus, S., Sokol, D.: Reconstructing parameterized strings from parameterized suffix and LCP arrays. Theoret. Comput. Sci. 981, 114230 (2024). https:\/\/doi.org\/10.1016\/j.tcs.2023.114230","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR3","doi-asserted-by":"publisher","unstructured":"Amir, A., Kondratovsky, E., Levy, A.: On suffix tree detection. In: Nardini, F.M., Pisanti, N., Venturini, R. (eds.) String Processing and Information Retrieval - 30th International Symposium, SPIRE 2023, Pisa, Italy, September 26-28, 2023, Proceedings. Lecture Notes in Computer Science, vol. 14240, pp. 14\u201327. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-43980-3_2","DOI":"10.1007\/978-3-031-43980-3_2"},{"issue":"1","key":"1_CR4","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1006\/jcss.1996.0003","volume":"52","author":"BS Baker","year":"1996","unstructured":"Baker, B.S.: Parameterized pattern matching: Algorithms and applications. J. Comput. Syst. Sci. 52(1), 28\u201342 (1996). https:\/\/doi.org\/10.1006\/jcss.1996.0003","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"1_CR5","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1137\/S0097539793246707","volume":"26","author":"BS Baker","year":"1997","unstructured":"Baker, B.S.: Parameterized duplication in strings: Algorithms and an application to software maintenance. SIAM J. Comput. 26(5), 1343\u20131362 (1997). https:\/\/doi.org\/10.1137\/S0097539793246707","journal-title":"SIAM J. Comput."},{"key":"1_CR6","doi-asserted-by":"publisher","unstructured":"Bannai, H., Inenaga, S., Shinohara, A., Takeda, M.: Inferring strings from graphs and arrays. In: Rovan, B., Vojt\u00e1s, P. (eds.) Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25\u201329, 2003, Proceedings. Lecture Notes in Computer Science, vol.\u00a02747, pp. 208\u2013217. Springer (2003). https:\/\/doi.org\/10.1007\/978-3-540-45138-9_15","DOI":"10.1007\/978-3-540-45138-9_15"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.jda.2012.05.004","volume":"16","author":"R Beal","year":"2012","unstructured":"Beal, R., Adjeroh, D.: Variations of the parameterized longest previous factor. J. Discret. Algorithm. 16, 129\u2013150 (2012)","journal-title":"J. Discret. Algorithm."},{"key":"1_CR8","unstructured":"Deguchi, S., Higashijima, F., Bannai, H., Inenaga, S., Takeda, M.: Parameterized suffix arrays for binary strings. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference 2008, Prague, Czech Republic, September 1-3, 2008. pp. 84\u201394. Prague Stringology Club, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague (2008). http:\/\/www.stringology.org\/event\/2008\/p08.html"},{"issue":"3","key":"1_CR9","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1051\/ita:2002012","volume":"36","author":"J Duval","year":"2002","unstructured":"Duval, J., Lefebvre, A.: Words over an ordered alphabet and suffix permutations. RAIRO Theor. Inf. Appl. 36(3), 249\u2013259 (2002). https:\/\/doi.org\/10.1051\/ita:2002012","journal-title":"RAIRO Theor. Inf. Appl."},{"key":"1_CR10","doi-asserted-by":"publisher","unstructured":"Fujisato, N., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Direct linear time construction of parameterized suffix and LCP arrays for constant alphabets. In: Brisaboa, N.R., Puglisi, S.J. (eds.) String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7-9, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11811, pp. 382\u2013391. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-32686-9_27","DOI":"10.1007\/978-3-030-32686-9_27"},{"key":"1_CR11","doi-asserted-by":"publisher","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: DeMillo, R.A. (ed.) Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA. pp. 135\u2013143. ACM (1984). https:\/\/doi.org\/10.1145\/800057.808675","DOI":"10.1145\/800057.808675"},{"issue":"2","key":"1_CR12","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00224-013-9522-8","volume":"54","author":"P Gawrychowski","year":"2014","unstructured":"Gawrychowski, P., Jez, A., Jez, L.: Validating the Knuth-Morris-Pratt failure function, fast and online. Theory Comput. Syst. 54(2), 337\u2013372 (2014). https:\/\/doi.org\/10.1007\/s00224-013-9522-8","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"1_CR13","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984). https:\/\/doi.org\/10.1137\/0213024","journal-title":"SIAM J. Comput."},{"key":"1_CR14","doi-asserted-by":"publisher","unstructured":"Jalsenius, M., Porat, B., Sach, B.: Parameterized matching in the streaming model. In: Portier, N., Wilke, T. (eds.) 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany. LIPIcs, vol.\u00a020, pp. 400\u2013411. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2013). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2013.400","DOI":"10.4230\/LIPIcs.STACS.2013.400"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.tcs.2022.11.032","volume":"942","author":"J K\u00e4rkk\u00e4inen","year":"2023","unstructured":"K\u00e4rkk\u00e4inen, J., Piatkowski, M., Puglisi, S.J.: String inference from longest-common-prefix array. Theoret. Comput. Sci. 942, 180\u2013199 (2023). https:\/\/doi.org\/10.1016\/j.tcs.2022.11.032","journal-title":"Theoret. Comput. Sci."},{"issue":"51","key":"1_CR16","doi-asserted-by":"publisher","first-page":"5347","DOI":"10.1016\/j.tcs.2009.09.011","volume":"410","author":"O Keller","year":"2009","unstructured":"Keller, O., Kopelowitz, T., Lewenstein, M.: On the longest common parameterized subsequence. Theoret. Comput. Sci. 410(51), 5347\u20135353 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR17","doi-asserted-by":"publisher","unstructured":"Kosaraju, S.R.: Faster algorithms for the construction of parameterized suffix trees (preliminary version). In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995. pp. 631\u2013637. IEEE Computer Society (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492664","DOI":"10.1109\/SFCS.1995.492664"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2022.09.008","volume":"933","author":"K Nakashima","year":"2022","unstructured":"Nakashima, K., Fujisato, N., Hendrian, D., Nakashima, Y., Yoshinaka, R., Inenaga, S., Bannai, H., Shinohara, A., Takeda, M.: Parameterized DAWGs: Efficient constructions and bidirectional pattern searches. Theoret. Comput. Sci. 933, 21\u201342 (2022)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR19","doi-asserted-by":"publisher","unstructured":"Nakashima, Y., Okabe, T., I, T., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from lyndon factorization. Theoret. Comput. Sci. 689, 147\u2013156 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2017.05.038","DOI":"10.1016\/j.tcs.2017.05.038"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-72200-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:01:54Z","timestamp":1726686114000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-72200-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"ISBN":["9783031721991","9783031722004"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-72200-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,9,19]]},"assertion":[{"value":"19 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Puerto Vallarta","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/computo.fismat.umich.mx\/spire2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}