{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T04:09:47Z","timestamp":1748491787368,"version":"3.41.0"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319199283"},{"type":"electronic","value":"9783319199290"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19929-0_30","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T13:09:49Z","timestamp":1434373789000},"page":"355-366","source":"Crossref","is-referenced-by-count":0,"title":["Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree"],"prefix":"10.1007","author":[{"given":"Yoshiaki","family":"Matsuoka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomohiro","family":"I","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"Claude, F., Farina, A., Mart\u00ednez-Prieto, M.A., Navarro, G.: Compressed $$q$$ q -gram indexing for highly repetitive biological sequences. In: Proceedings of the BIBE 2010, pp. 86\u201391 (2010)","DOI":"10.1109\/BIBE.2010.22"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time. In: FOCS, pp. 75\u201384. IEEE Computer Society (1975)","DOI":"10.1109\/SFCS.1975.26"},{"issue":"3","key":"30_CR3","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0097539795286119","volume":"27","author":"P Ferragina","year":"1998","unstructured":"Ferragina, P., Grossi, R.: Optimal on-line search and sublinear time update in string matching. SIAM J. Comput. 27(3), 713\u2013736 (1998)","journal-title":"SIAM J. Comput."},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: FOCS, pp. 390\u2013398. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"30_CR5","unstructured":"Gupta, A., Hon, W.K., Shah, R., Vitter, J.S.: Dynamic rank\/select dictionaries with applications to XML indexing. Technical report 06\u2013014, Purdue University (2006)"},{"key":"30_CR6","unstructured":"Hon, W.K., Lam, T.W., Sadakane, K., Sung, W.K., Yiu, S.M.: Compressed index for dynamic text. In: Data Compression Conference, pp. 102\u2013111 (2004)"},{"key":"30_CR7","unstructured":"Leiserson, C.E., Prokop, H., Randall, K.H.: Using de Bruijn sequences to index a 1 in a computer word (1998) (unpublished manuscript)"},{"issue":"1","key":"30_CR8","first-page":"40","volume":"12","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nord. J. Comput. 12(1), 40\u201366 (2005)","journal-title":"Nord. J. Comput."},{"issue":"5","key":"30_CR9","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"30_CR10","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S1570-8667(03)00066-2","volume":"2","author":"G Navarro","year":"2004","unstructured":"Navarro, G.: Indexing text using the Ziv-Lempel trie. J. Discret. Algorithms 2(1), 87\u2013114 (2004)","journal-title":"J. Discret. Algorithms"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. In: Proceedings of the SODA 2013, pp. 865\u2013876 (2013)","DOI":"10.1137\/1.9781611973105.62"},{"issue":"2","key":"30_CR12","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1089\/cmb.2006.13.296","volume":"13","author":"KR Rasmussen","year":"2006","unstructured":"Rasmussen, K.R., Stoye, J., Myers, E.W.: Efficient $$q$$ q -gram filters for finding all $$\\epsilon $$ \u03f5 -matches over a given length. J. Comput. Biol. 13(2), 296\u2013308 (2006)","journal-title":"J. Comput. Biol."},{"issue":"2","key":"30_CR13","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.jda.2009.02.007","volume":"8","author":"M Salson","year":"2010","unstructured":"Salson, M., Lecroq, T., L\u00e9onard, M., Mouchard, L.: Dynamic extended suffix arrays. J. Discret. Algorithms 8(2), 241\u2013257 (2010)","journal-title":"J. Discret. Algorithms"},{"issue":"3","key":"30_CR14","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(3), 249\u2013260 (1995)","journal-title":"Algorithmica"},{"key":"30_CR15","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)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"2","key":"30_CR16","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"DE Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space $$\\Theta (N)$$ \u0398 ( N ) . Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19929-0_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T16:58:22Z","timestamp":1748451502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-19929-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319199283","9783319199290"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19929-0_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}