{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T04:16:40Z","timestamp":1743135400370,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031826962"},{"type":"electronic","value":"9783031826979"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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-82697-9_21","type":"book-chapter","created":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T10:17:33Z","timestamp":1739614653000},"page":"284-297","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Packed Acyclic Deterministic Finite Automata"],"prefix":"10.1007","author":[{"given":"Hiroki","family":"Shibata","sequence":"first","affiliation":[]},{"given":"Masakazu","family":"Ishihata","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,16]]},"reference":[{"key":"21_CR1","unstructured":"Geonames dump. https:\/\/download.geonames.org\/export\/dump\/"},{"key":"21_CR2","unstructured":"Laboratory for web algorithmics. https:\/\/law.di.unimi.it\/datasets.php"},{"issue":"9","key":"21_CR3","doi-asserted-by":"publisher","first-page":"1066","DOI":"10.1109\/32.31365","volume":"15","author":"J Aoe","year":"1989","unstructured":"Aoe, J.: An efficient digital search algorithm by using a double-array structure. IEEE Trans. Software Eng. 15(9), 1066\u20131077 (1989). https:\/\/doi.org\/10.1109\/32.31365","journal-title":"IEEE Trans. Software Eng."},{"issue":"5","key":"21_CR4","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1145\/42411.42420","volume":"31","author":"AW Appel","year":"1988","unstructured":"Appel, A.W., Jacobson, G.J.: The world\u2019s fastest scrabble program. Commun. ACM 31(5), 572\u2013578 (1988). https:\/\/doi.org\/10.1145\/42411.42420","journal-title":"Commun. ACM"},{"issue":"3","key":"21_CR5","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"SW Bent","year":"1985","unstructured":"Bent, S.W., Sleator, D.D., Tarjan, R.E.: Biased search trees. SIAM J. Comput. 14(3), 545\u2013568 (1985). https:\/\/doi.org\/10.1137\/0214041","journal-title":"SIAM J. Comput."},{"key":"21_CR6","doi-asserted-by":"publisher","unstructured":"Bille, P., G\u00f8rtz, I.L., Skjoldjensen, F.R.: Deterministic indexing for packed strings. In: K\u00e4rkk\u00e4inen, J., Radoszewski, J., Rytter, W. (eds.) 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, 4\u20136 July 2017, Warsaw, Poland. LIPIcs, vol.\u00a078, pp. 6:1\u20136:11. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2017.6","DOI":"10.4230\/LIPIcs.CPM.2017.6"},{"issue":"3","key":"21_CR7","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2015","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44(3), 513\u2013539 (2015). https:\/\/doi.org\/10.1137\/130936889","journal-title":"SIAM J. Comput."},{"key":"21_CR8","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. Theor. Comput. Sci. 40, 31\u201355 (1985). https:\/\/doi.org\/10.1016\/0304-3975(85)90157-4","journal-title":"Theor. Comput. Sci."},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Boldi, P., Codenotti, B., Santini, M., Vigna, S.: Ubicrawler: a scalable fully distributed web crawler. Softw. Pract. Exp. 34(8), 711\u2013726 (2004)","DOI":"10.1002\/spe.587"},{"key":"21_CR10","doi-asserted-by":"publisher","unstructured":"Daciuk, J., Mihov, S., Watson, B.W., Watson, R.E.: Incremental construction of minimal acyclic finite state automata. Comput. Linguist. 26(1), 3\u201316 (2000). https:\/\/doi.org\/10.1162\/089120100561601","DOI":"10.1162\/089120100561601"},{"key":"21_CR11","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Grossi, R., Gupta, A., Shah, R., Vitter, J.S.: On searching compressed string collections cache-obliviously. In: Lenzerini, M., Lembo, D. (eds.) Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, 9\u201311 June 2008, Vancouver, BC, Canada, pp. 181\u2013190. ACM (2008). https:\/\/doi.org\/10.1145\/1376916.1376943","DOI":"10.1145\/1376916.1376943"},{"key":"21_CR12","unstructured":"Ferragina, P., Navarro, G.: Pizza &chili corpus. https:\/\/pizzachili.dcc.uchile.cl\/"},{"issue":"3","key":"21_CR13","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"ML Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424\u2013436 (1993). https:\/\/doi.org\/10.1016\/0022-0000(93)90040-4","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR14","doi-asserted-by":"publisher","unstructured":"Fujita, Y., Ichihashi, Y., Kanda, S., Morita, K., Fuketa, M.: Full-text search using double-array CDAWG. Int. J. Future Comput. Commun. 5(6), 237\u2013240 (2016). https:\/\/doi.org\/10.18178\/ijfcc.2016.5.6.478","DOI":"10.18178\/ijfcc.2016.5.6.478"},{"key":"21_CR15","doi-asserted-by":"publisher","unstructured":"Ganardi, M., Jez, A., Lohrey, M.: Balancing straight-line programs. J. ACM 68(4), 27:1\u201327:40 (2021). https:\/\/doi.org\/10.1145\/3457389","DOI":"10.1145\/3457389"},{"key":"21_CR16","doi-asserted-by":"publisher","unstructured":"Kanda, S., K\u00f6ppl, D., Tabei, Y., Morita, K., Fuketa, M.: Dynamic path-decomposed tries. ACM J. Exp. Algorithmics 25, 1\u201328 (2020). https:\/\/doi.org\/10.1145\/3418033","DOI":"10.1145\/3418033"},{"key":"21_CR17","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley (1973)"},{"key":"21_CR18","doi-asserted-by":"publisher","unstructured":"Morrison, D.R.: PATRICIA - practical algorithm to retrieve information coded in alphanumeric. J. ACM 15(4), 514\u2013534 (1968). https:\/\/doi.org\/10.1145\/321479.321481","DOI":"10.1145\/321479.321481"},{"key":"21_CR19","doi-asserted-by":"publisher","unstructured":"Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16:1\u201316:39 (2014). https:\/\/doi.org\/10.1145\/2601073","DOI":"10.1145\/2601073"},{"key":"21_CR20","doi-asserted-by":"publisher","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ARY trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007). https:\/\/doi.org\/10.1145\/1290672.1290680","DOI":"10.1145\/1290672.1290680"},{"key":"21_CR21","doi-asserted-by":"publisher","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983). https:\/\/doi.org\/10.1016\/0022-0000(83)90006-5","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"21_CR22","doi-asserted-by":"publisher","unstructured":"Takagi, T., Inenaga, S., Sadakane, K., Arimura, H.: Packed compact tries: a fast and efficient data structure for online string processing. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 100-A(9), 1785\u20131793 (2017). https:\/\/doi.org\/10.1587\/transfun.E100.A.1785","DOI":"10.1587\/transfun.E100.A.1785"},{"key":"21_CR23","doi-asserted-by":"publisher","unstructured":"Tsuruta, K., et al.: c-trie++: a dynamic trie tailored for fast prefix searches. Inf. Comput. 285(Part), 104794 (2022). https:\/\/doi.org\/10.1016\/j.ic.2021.104794","DOI":"10.1016\/j.ic.2021.104794"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82697-9_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T10:17:37Z","timestamp":1739614657000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82697-9_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826962","9783031826979"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82697-9_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"16 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}