{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T11:53:40Z","timestamp":1752666820357,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319199283"},{"type":"electronic","value":"9783319199290"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-19929-0_14","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T13:09:49Z","timestamp":1434373789000},"page":"160-171","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Alphabet-Dependent String Searching with Wexponential Search Trees"],"prefix":"10.1007","author":[{"given":"Johannes","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"issue":"4","key":"14_CR1","doi-asserted-by":"publisher","first-page":"1396","DOI":"10.1137\/110836377","volume":"43","author":"A Amir","year":"2014","unstructured":"Amir, A., Franceschini, G., Grossi, R., Kopelowitz, T., Lewenstein, M., Lewenstein, N.: Managing unbounded-length keys in comparison-driven data structures with applications to online indexing. SIAM J. Comput. 43(4), 1396\u20131416 (2014)","journal-title":"SIAM J. Comput."},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Andersson, A., Thorup, M.: Dynamic ordered sets with exponential search trees. J. ACM 53(3) (2007). Article No. 13","DOI":"10.1145\/1236457.1236460"},{"issue":"1","key":"14_CR3","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P Beame","year":"2002","unstructured":"Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci. 65(1), 38\u201372 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-45465-9_18","volume-title":"Automata, Languages and Programming","author":"MA Bender","year":"2002","unstructured":"Bender, M.A., Cole, R., Raman, R.: Exponential structures for efficient cache-oblivious algorithms. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 195\u2013207. Springer, Heidelberg (2002)"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.jda.2012.07.003","volume":"18","author":"D Breslauer","year":"2013","unstructured":"Breslauer, D., Italiano, G.F.: Near real-time suffix tree construction via the fringe marked ancestor problem. J. Discrete Algorithms 18, 32\u201348 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/11786986_32","volume-title":"Automata, Languages and Programming","author":"R Cole","year":"2006","unstructured":"Cole, R., Kopelowitz, T., Lewenstein, M.: Suffix trays and suffix trists: structures for faster text indexing. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 358\u2013369. Springer, Heidelberg (2006)"},{"key":"14_CR7","unstructured":"Fischer, J., Gawrychowski, P.: Alphabet-dependent string searching with wexponential search trees. CoRR abs\/1302.3347 (2013). http:\/\/arxiv.org\/abs\/1302.3347"},{"issue":"3","key":"14_CR8","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with $${O}(1)$$ worst case access time. J. ACM 31(3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Kopelowitz, T.: On-line indexing for general alphabets via predecessor queries on subsets of an ordered list. In: Proceedings of the FOCS, pp. 283\u2013292. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.79"},{"key":"14_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1007\/978-3-642-39206-1_55","volume-title":"Automata, Languages, and Programming","author":"G Kucherov","year":"2013","unstructured":"Kucherov, G., Nekrich, Y.: Full-fledged real-time indexing for constant size alphabets. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 650\u2013660. Springer, Heidelberg (2013)"},{"issue":"5","key":"14_CR11","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":"2","key":"14_CR12","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(2), 262\u2013272 (1976)","journal-title":"J. ACM"},{"issue":"2","key":"14_CR13","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1137\/0208014","volume":"8","author":"K Mehlhorn","year":"1979","unstructured":"Mehlhorn, K.: Dynamic binary search. SIAM J. Comput. 8(2), 175\u2013198 (1979)","journal-title":"SIAM J. Comput."},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-540-70575-8_8","volume-title":"Automata, Languages and Programming","author":"M Ru\u017ei\u0107","year":"2008","unstructured":"Ru\u017ei\u0107, M.: Constructing efficient dictionaries in close to sorting time. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 84\u201395. Springer, Heidelberg (2008)"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the Annual Symposium on Switching and Automata Theory, pp. 1\u201311. IEEE Computer Society (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19929-0_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:35:53Z","timestamp":1676018153000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19929-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319199283","9783319199290"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19929-0_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}