{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:49:47Z","timestamp":1742950187682,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"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_15","type":"book-chapter","created":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:01:50Z","timestamp":1726686110000},"page":"192-203","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["All-Pairs Suffix-Prefix on\u00a0Dynamic Set of\u00a0Strings"],"prefix":"10.1007","author":[{"given":"Masaru","family":"Kikuchi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1833-010X","authenticated-orcid":false,"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"issue":"1","key":"15_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"MI Abouelhoda","year":"2004","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms 2(1), 53\u201386 (2004)","journal-title":"J. Discrete Algorithms"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18, 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-63165-8_184","volume-title":"Automata, Languages and Programming","author":"S Alstrup","year":"1997","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Minimizing diameters of dynamic trees. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 270\u2013280. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63165-8_184"},{"key":"15_CR4","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.I.: The smallest automaton recognizing the subwords of a text. Theoret. Comput. Sci. 40, 31\u201355 (1985)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"15_CR5","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). https:\/\/doi.org\/10.1145\/28869.28873","journal-title":"J. ACM"},{"key":"15_CR6","unstructured":"C\u00e1novas, R., Cazaux, B., Rivals, E.: The compressed overlap index. CoRR arXiv:1707.05613 (2017)"},{"issue":"2","key":"15_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.ipl.2005.11.019","volume":"98","author":"S Dori","year":"2006","unstructured":"Dori, S., Landau, G.M.: Construction of Aho Corasick automaton in linear time for integer alphabets. Inf. Process. Lett. 98(2), 66\u201372 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"15_CR8","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1145\/355541.355547","volume":"47","author":"M Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM 47(6), 987\u20131011 (2000)","journal-title":"J. ACM"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574931"},{"issue":"4","key":"15_CR10","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0020-0190(92)90176-V","volume":"41","author":"D Gusfield","year":"1992","unstructured":"Gusfield, D., Landau, G.M., Schieber, B.: An efficient algorithm for the all pairs suffix-prefix problem. Inf. Process. Lett. 41(4), 181\u2013185 (1992)","journal-title":"Inf. Process. Lett."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/j.tcs.2018.04.016","volume":"792","author":"D Hendrian","year":"2019","unstructured":"Hendrian, D., Inenaga, S., Yoshinaka, R., Shinohara, A.: Efficient dynamic dictionary matching with DAWGs and AC-automata. Theor. Comput. Sci. 792, 161\u2013172 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR12","unstructured":"Khan, S.: Optimal construction of hierarchical overlap graphs. In: CPM 2021. LIPIcs, vol.\u00a0191, pp. 17:1\u201317:11 (2021)"},{"issue":"2","key":"15_CR13","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.tcs.2017.07.013","volume":"698","author":"J Lim","year":"2017","unstructured":"Lim, J., Park, K.: A fast algorithm for the all-pairs suffix-prefix problem. Theor. Comput. Sci. 698, 14\u201324 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"106275","DOI":"10.1016\/j.ipl.2022.106275","volume":"178","author":"G Loukides","year":"2022","unstructured":"Loukides, G., Pissis, S.P.: All-pairs suffix\/prefix in optimal time using Aho-Corasick space. Inf. Process. Lett. 178, 106275 (2022)","journal-title":"Inf. Process. Lett."},{"key":"15_CR16","unstructured":"Loukides, G., Pissis, S.P., Thankachan, S.V., Zuba, W.: Suffix-prefix queries on a dictionary. In: CPM 2023. LIPIcs, vol.\u00a0259, pp. 21:1\u201321:20 (2023)"},{"issue":"5","key":"15_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."},{"issue":"3","key":"15_CR18","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.ipl.2009.10.015","volume":"110","author":"E Ohlebusch","year":"2010","unstructured":"Ohlebusch, E., Gog, S.: Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem. Inf. Process. Lett. 110(3), 123\u2013128 (2010)","journal-title":"Inf. Process. Lett."},{"key":"15_CR19","unstructured":"Park, S., Park, S.G., Cazaux, B., Park, K., Rivals, E.: A linear time algorithm for constructing hierarchical overlap graphs. In: CPM 2021. LIPIcs, vol.\u00a0191, pp. 22:1\u201322:9 (2021)"},{"issue":"5","key":"15_CR20","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1007\/s00453-019-00646-w","volume":"82","author":"T Takagi","year":"2020","unstructured":"Takagi, T., Inenaga, S., Arimura, H., Breslauer, D., Hendrian, D.: Fully-online suffix tree and directed acyclic word graph construction for multiple texts. Algorithmica 82(5), 1346\u20131377 (2020)","journal-title":"Algorithmica"},{"key":"15_CR21","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jda.2016.04.002","volume":"37","author":"WHA Tustumi","year":"2016","unstructured":"Tustumi, W.H.A., Gog, S., Telles, G.P., Louza, F.A.: An improved algorithm for the all-pairs suffix-prefix problem. J. Discrete Algorithms 37, 34\u201343 (2016)","journal-title":"J. Discrete Algorithms"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Westbrook, J.R.: Fast incremental planarity testing. In: ICALP 1992. Lecture Notes in Computer Science, vol.\u00a0623, pp. 342\u2013353 (1992)","DOI":"10.1007\/3-540-55719-9_86"}],"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_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:02:43Z","timestamp":1726686163000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-72200-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"ISBN":["9783031721991","9783031722004"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-72200-4_15","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":"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"}}]}}