{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T21:24:55Z","timestamp":1791581095973,"version":"4.3.4"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031439797","type":"print"},{"value":"9783031439803","type":"electronic"}],"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-43980-3_2","type":"book-chapter","created":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T12:02:15Z","timestamp":1695124935000},"page":"14-27","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Suffix Tree Detection"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3939-337X","authenticated-orcid":false,"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9625-7534","authenticated-orcid":false,"given":"Eitan","family":"Kondratovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1686-0094","authenticated-orcid":false,"given":"Avivit","family":"Levy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,9,20]]},"reference":[{"issue":"1","key":"2_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2390176.2390189","volume":"9","author":"A Amir","year":"2012","unstructured":"Amir, A., Eisenberg, E., Levy, A., Porat, E., Shapira, N.: Cycle detection and correction. ACM Trans. Algorithms 9(1), 1\u201320 (2012). https:\/\/doi.org\/10.1145\/2390176.2390189","journal-title":"ACM Trans. Algorithms"},{"issue":"7","key":"2_CR2","doi-asserted-by":"publisher","first-page":"2857","DOI":"10.1007\/s00453-019-00559-8","volume":"81","author":"A Amir","year":"2019","unstructured":"Amir, A., Levy, A., Lewenstein, M., Lubin, R., Porat, B.: Can we recover the cover? Algorithmica 81(7), 2857\u20132875 (2019). https:\/\/doi.org\/10.1007\/s00453-019-00559-8","journal-title":"Algorithmica"},{"key":"2_CR3","series-title":"NATO ASI Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-82456-2_6","volume-title":"Combinatorial Algorithms on Words","author":"A Apostolico","year":"1985","unstructured":"Apostolico, A.: The myriad virtues of subword trees. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words. NATO ASI Series, vol. 12, pp. 85\u201396. Springer, Heidelberg (1985). https:\/\/doi.org\/10.1007\/978-3-642-82456-2_6"},{"key":"2_CR4","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":"2_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2012.07.018","volume":"457","author":"D Breslauer","year":"2012","unstructured":"Breslauer, D., Italiano, G.F.: On suffix extensions in suffix trees. Theoret. Comput. Sci. 457, 27\u201334 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.jda.2014.07.002","volume":"28","author":"B Cazaux","year":"2014","unstructured":"Cazaux, B., Rivals, E.: Reverse engineering of compact suffix trees and links: a novel algorithm. J. Discrete Algorithms 28, 9\u201322 (2014)","journal-title":"J. Discrete Algorithms"},{"key":"2_CR7","unstructured":"Cl\u00e9ment, J., Crochemore, M., Rindone, G.: Reverse engineering prefix tables. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science STACS. LIPIcs, vol. 3, pp. 289\u2013300. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2009)"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-642-13509-5_23","volume-title":"Combinatorial Pattern Matching","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Iliopoulos, C.S., Pissis, S.P., Tischler, G.: Cover array string reconstruction. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 251\u2013259. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13509-5_23"},{"issue":"2","key":"2_CR9","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1051\/ita:2008030","volume":"43","author":"J Duval","year":"2009","unstructured":"Duval, J., Lecroq, T., Lefebvre, A.: Efficient validation and construction of border arrays and validation of string matching automata. RAIRO Theor. Inform. Appl. 43(2), 281\u2013297 (2009)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: Proceedings of the 38th IEEE Symposium on Foundations of Computer Science, pp. 137\u2013143 (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"key":"2_CR11","first-page":"223","volume":"42","author":"F Franek","year":"2000","unstructured":"Franek, F., et al.: Verifying a border array in linear time. J. Comb. Math. Comb. Comput. 42, 223\u2013236 (2000)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"2","key":"2_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)","journal-title":"Theory Comput. Syst."},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.tcs.2019.10.027","volume":"812","author":"P Gawrychowski","year":"2020","unstructured":"Gawrychowski, P., Kociumaka, T., Radoszewski, J., Rytter, W., Walen, T.: Universal reconstruction of a string. Theor. Comput. Sci. 812, 174\u2013186 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"6\u20137","key":"2_CR14","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1142\/S0129054119400276","volume":"30","author":"K Gelle","year":"2019","unstructured":"Gelle, K., Iv\u00e1n, S.: Recognizing union-find trees is NP-complete, even without rank info. Int. J. Found. Comput. Sci. 30(6\u20137), 1029\u20131045 (2019)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"key":"2_CR16","unstructured":"He, M., Munro, J.I., Rao, S.S.: A categorization theorem on suffix arrays with applications to space efficient text indexes. In: SODA, vol. 5, pp. 23\u201332. Citeseer (2005)"},{"issue":"50","key":"2_CR17","doi-asserted-by":"publisher","first-page":"6959","DOI":"10.1016\/j.tcs.2011.09.008","volume":"412","author":"I Tomohiro","year":"2011","unstructured":"Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Verifying and enumerating parameterized border arrays. Theor. Comput. Sci. 412(50), 6959\u20136981 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1016\/j.dam.2013.02.033","volume":"163","author":"I Tomohiro","year":"2014","unstructured":"Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from suffix trees and links on a binary alphabet. Discrete Appl. Math. 163, 316\u2013325 (2014)","journal-title":"Discrete Appl. Math."},{"key":"2_CR19","unstructured":"K\u00e4rkk\u00e4inen, J., Piatkowski, M., Puglisi, S.J.: String inference from longest-common-prefix array. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP. LIPIcs, vol. 80, pp. 62:1\u201362:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"issue":"22","key":"2_CR20","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1016\/j.ipl.2013.09.009","volume":"113","author":"G Kucherov","year":"2013","unstructured":"Kucherov, G., T\u00f3thm\u00e9r\u00e9sz, L., Vialette, S.: On the combinatorics of suffix arrays. Inf. Process. Lett. 113(22), 915\u2013920 (2013)","journal-title":"Inf. Process. Lett."},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"EM McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23, 262\u2013272 (1976)","journal-title":"J. ACM"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.tcs.2017.05.038","volume":"689","author":"Y Nakashima","year":"2017","unstructured":"Nakashima, Y., Okabe, T., Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from Lyndon factorization. Theor. Comput. Sci. 689, 147\u2013156 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"2_CR23","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.tcs.2008.01.011","volume":"395","author":"KB Sch\u00fcrmann","year":"2008","unstructured":"Sch\u00fcrmann, K.B., Stoye, J.: Counting suffix arrays and strings. Theoret. Comput. Sci. 395(2\u20133), 220\u2013234 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.jda.2015.01.005","volume":"32","author":"T Starikovskaya","year":"2015","unstructured":"Starikovskaya, T., Vildh\u00f8j, H.W.: A suffix tree or not a suffix tree? J. Discrete Algorithms 32, 14\u201323 (2015)","journal-title":"J. Discrete Algorithms"},{"key":"2_CR25","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, 249\u2013260 (1995)","journal-title":"Algorithmica"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proceedings of the 14 IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"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-43980-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T10:40:17Z","timestamp":1730112017000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43980-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031439797","9783031439803"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43980-3_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"20 September 2023","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":"Pisa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","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":"26 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spire2023.isti.cnr.it\/","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":"47","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":"31","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":"66% - 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","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)"}}]}}