{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:28:32Z","timestamp":1743046112591,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031206429"},{"type":"electronic","value":"9783031206436"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-20643-6_5","type":"book-chapter","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T13:18:09Z","timestamp":1667222289000},"page":"55-69","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Reconstructing Parameterized Strings from\u00a0Parameterized Suffix and\u00a0LCP Arrays"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[]},{"given":"Concettina","family":"Guerra","sequence":"additional","affiliation":[]},{"given":"Eitan","family":"Kondratovsky","sequence":"additional","affiliation":[]},{"given":"Gad M.","family":"Landau","sequence":"additional","affiliation":[]},{"given":"Shoshana","family":"Marcus","sequence":"additional","affiliation":[]},{"given":"Dina","family":"Sokol","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,1]]},"reference":[{"issue":"5","key":"5_CR1","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1137\/S0097539702424496","volume":"35","author":"A Amir","year":"2006","unstructured":"Amir, A., Aumann, A., Lewenstein, M., Porat, E.: Function matching. SIAM J. Comput. 35(5), 1007\u20131022 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"5_CR2","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1137\/S0097539792226321","volume":"23","author":"A Amir","year":"1994","unstructured":"Amir, A., Benson, G., Farach, M.: An alphabet independent approach to two dimensional pattern matching. SIAM J. Comp. 23(2), 313\u2013323 (1994)","journal-title":"SIAM J. Comp."},{"key":"5_CR3","unstructured":"Amir, A., Church, K.W., Dar, E.: Separable attributes: a technique for solving the submatrices character count problem. In: Proceedings 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 400\u2013401 (2002)"},{"issue":"3","key":"5_CR4","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(94)90086-8","volume":"49","author":"A Amir","year":"1994","unstructured":"Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized matching. Inf. Process. Lett. 49(3), 111\u2013115 (1994). https:\/\/doi.org\/10.1016\/0020-0190(94)90086-8","journal-title":"Inf. Process. Lett."},{"key":"5_CR5","doi-asserted-by":"publisher","unstructured":"Amir, A., Kondratovsky, E.: Sufficient conditions for efficient indexing under different matchings. In: Pisanti, N., Pissis, S.P. (eds.) 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, 18\u201320 June 2019, Pisa, Italy. LIPIcs, vol. 128, pp. 6:1\u20136:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2019.6","DOI":"10.4230\/LIPIcs.CPM.2019.6"},{"key":"5_CR6","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. Theor. Comput. Sci. 852, 132\u2013137 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2020.11.023","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"5_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.jda.2006.03.014","volume":"5","author":"A Apostolico","year":"2007","unstructured":"Apostolico, A., Erd\u00f6s, P.L., Lewenstein, M.: Parameterized matching with mismatches. J. Discrete Algorithms 5(1), 135\u2013140 (2007). https:\/\/doi.org\/10.1016\/j.jda.2006.03.014","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"5_CR8","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01215882","volume":"1","author":"G Babu","year":"1995","unstructured":"Babu, G., Mehtre, B., Kankanhalli, M.: Color indexing for efficient image retrieval. Multimedia Tools Appl. 1(4), 327\u2013348 (1995)","journal-title":"Multimedia Tools Appl."},{"issue":"1","key":"5_CR9","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":"5_CR10","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":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-45138-9_15","volume-title":"Mathematical Foundations of Computer Science 2003","author":"H Bannai","year":"2003","unstructured":"Bannai, H., Inenaga, S., Shinohara, A., Takeda, M.: Inferring strings from graphs and arrays. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 208\u2013217. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45138-9_15"},{"key":"5_CR12","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, 1\u20133 September 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":"5_CR13","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. Inform. Appl. 36(3), 249\u2013259 (2002). https:\/\/doi.org\/10.1051\/ita:2002012","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-030-32686-9_27","volume-title":"String Processing and Information Retrieval","author":"N Fujisato","year":"2019","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.) SPIRE 2019. LNCS, vol. 11811, pp. 382\u2013391. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-32686-9_27"},{"key":"5_CR15","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":"5_CR16","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":"5_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/978-3-540-30140-0_38","volume-title":"Algorithms \u2013 ESA 2004","author":"C Hazay","year":"2004","unstructured":"Hazay, C., Lewenstein, M., Sokol, D.: Approximate parameterized matching. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 414\u2013425. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30140-0_38"},{"key":"5_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/3-540-58094-8_20","volume-title":"Combinatorial Pattern Matching","author":"RM Idury","year":"1994","unstructured":"Idury, R.M., Sch\u00e4ffer, A.A.: Multiple matching of parameterized patterns. In: Crochemore, M., Gusfield, D. (eds.) CPM 1994. LNCS, vol. 807, pp. 226\u2013239. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-58094-8_20"},{"key":"5_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-642-03784-9_4","volume-title":"String Processing and Information Retrieval","author":"T Lee","year":"2009","unstructured":"Lee, T., Na, J.C., Park, K.: On-line construction of parameterized suffix trees. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 31\u201338. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03784-9_4"},{"issue":"1","key":"5_CR20","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF00130487","volume":"7","author":"M Swain","year":"1991","unstructured":"Swain, M., Ballard, D.: Color indexing. Int. J. Comput. Vision 7(1), 11\u201332 (1991)","journal-title":"Int. J. Comput. Vision"}],"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-20643-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T13:19:18Z","timestamp":1667222358000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-20643-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031206429","9783031206436"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-20643-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 November 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"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":"Concepci\u00f3n","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chile","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spire2022.inf.udec.cl\/","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":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","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":"23","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":"53% - 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":"3.62","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)"}}]}}