{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:58Z","timestamp":1759639078451,"version":"3.37.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030004781"},{"type":"electronic","value":"9783030004798"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-00479-8_21","type":"book-chapter","created":{"date-parts":[[2018,9,13]],"date-time":"2018-09-13T10:58:18Z","timestamp":1536836298000},"page":"254-267","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays"],"prefix":"10.1007","author":[{"given":"Yuki","family":"Kuhara","sequence":"first","affiliation":[]},{"given":"Yuto","family":"Nakashima","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,14]]},"reference":[{"key":"21_CR1","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"},{"issue":"3","key":"21_CR2","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A Blumer","year":"1987","unstructured":"Blumer, A., Blumer, J., Haussler, D., Mcconnell, R., Ehrenfeucht, A.: Complete inverted files for efficient text retrieval and analysis. J. ACM 34(3), 578\u2013595 (1987)","journal-title":"J. ACM"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(85)90157-4","volume":"40","author":"A Blumer","year":"1985","unstructured":"Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M.T., Seiferas, J.: The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci. 40, 31\u201355 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR4","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. Discret. Algorithms 28, 9\u201322 (2014)","journal-title":"J. Discret. Algorithms"},{"unstructured":"Cl\u00e9ment, J., Crochemore, M., Rindone, G.: Reverse engineering prefix tables. In: Proceedings of 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp. 289\u2013300 (2009)","key":"21_CR5"},{"key":"21_CR6","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"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.tcs.2017.04.008","volume":"710","author":"JW Daykin","year":"2018","unstructured":"Daykin, J.W., Franek, F., Holub, J., Islam, A.S., Smyth, W.: Reconstructing a string from its Lyndon arrays. Theor. Comput. Sci. 710, 44\u201351 (2018)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"21_CR8","first-page":"281","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. ITA 43(2), 281\u2013297 (2009)","journal-title":"ITA"},{"issue":"3","key":"21_CR9","first-page":"249","volume":"36","author":"J Duval","year":"2002","unstructured":"Duval, J., Lefebvre, A.: Words over an ordered alphabet and suffix permutations. ITA 36(3), 249\u2013259 (2002)","journal-title":"ITA"},{"issue":"2","key":"21_CR10","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00224-013-9522-8","volume":"54","author":"P Gawrychowski","year":"2014","unstructured":"Gawrychowski, P., Je\u017c, A., Je\u017c, L.: Validating the Knuth-Morris-Pratt failure function, fast and online. Theor. Comput. Syst. 54(2), 337\u2013372 (2014)","journal-title":"Theor. Comput. Syst."},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/978-3-642-22300-6_41","volume-title":"Algorithms and Data Structures","author":"J He","year":"2011","unstructured":"He, J., Liang, H., Yang, G.: Reversing longest previous factor tables is hard. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 488\u2013499. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22300-6_41"},{"key":"21_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-16321-0_13","volume-title":"String Processing and Information Retrieval","author":"T I","year":"2010","unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Counting and verifying maximal palindromes. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 135\u2013146. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16321-0_13"},{"unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from suffix trees and links on a binary alphabet. In: Proceedings of the Prague Stringology Conference 2011, pp. 121\u2013130 (2011)","key":"21_CR13"},{"issue":"50","key":"21_CR14","doi-asserted-by":"publisher","first-page":"6959","DOI":"10.1016\/j.tcs.2011.09.008","volume":"412","author":"T I","year":"2011","unstructured":"I, T., 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."},{"unstructured":"K\u00e4rkk\u00e4inen, J., Piatkowski, M., Puglisi, S.J.: String inference from longest-common-prefix array. In: Proceedings of 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 62:1\u201362:14 (2017)","key":"21_CR15"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0377-0427(01)00577-5","volume":"42","author":"W Lu","year":"2002","unstructured":"Lu, W., Ryan, P.J., Smyth, W.F., Sun, Y., Yang, L.: Verifying a border array in linear time. J. Comb. Math. Comb. Comput 42, 223\u2013236 (2002)","journal-title":"J. Comb. Math. Comb. Comput"},{"issue":"5","key":"21_CR17","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"unstructured":"Matsubara, W., Ishino, A., Shinohara, A.: Inferring strings from runs. In: Proceedings of the Prague Stringology Conference vol. 2010, pp. 150\u2013160 (2010)","key":"21_CR18"},{"issue":"2","key":"21_CR19","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"EM McCreight","year":"1985","unstructured":"McCreight, E.M.: Priority search trees. SIAM J. Comput. 14(2), 257\u2013276 (1985)","journal-title":"SIAM J. Comput."},{"key":"21_CR20","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., I, T., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from Lyndon factorization. Theor. Comput. Sci. 689, 147\u2013156 (2017)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Nakashima, Y., Takagi, T., Inenaga, S., Bannai, H., Takeda, M.: On reverse engineering the Lyndon tree. In: Proceedings of the Prague Stringology Conference vol. 2017, pp. 108\u2013117 (2017)","key":"21_CR21"},{"key":"21_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1007\/978-3-662-48971-0_64","volume-title":"Algorithms and Computation","author":"M Nishida","year":"2015","unstructured":"Nishida, M., I., T., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from full abelian periods. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 768\u2013779. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_64"},{"issue":"2\u20133","key":"21_CR23","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.tcs.2008.01.011","volume":"395","author":"K Sch\u00fcrmann","year":"2008","unstructured":"Sch\u00fcrmann, K., Stoye, J.: Counting suffix arrays and strings. Theor. Comput. Sci. 395(2\u20133), 220\u2013234 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR24","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.jda.2015.01.005","volume":"32","author":"TA Starikovskaya","year":"2015","unstructured":"Starikovskaya, T.A., Vildh\u00f8j, H.W.: A suffix tree or not a suffix tree? J. Discrete Algorithms 32, 14\u201323 (2015)","journal-title":"J. Discrete Algorithms"},{"unstructured":"Stoye, J.: Affix trees. Technical report 2000-04, Universit\u00e4t Bielefeld, Technische Fakult\u00e4t (2000)","key":"21_CR25"},{"doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern-matching algorithms. In: Proceedings of 14th IEEE Annual Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","key":"21_CR26","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-00479-8_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,24]],"date-time":"2019-10-24T01:17:31Z","timestamp":1571879851000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-00479-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030004781","9783030004798"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-00479-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"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":"Lima","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Peru","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 October 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 October 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/eventos.spc.org.pe\/spire2018\/","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"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"51","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"22","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"6","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"43% - 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"}},{"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"}},{"value":"3.8","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}}]}}