{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T19:54:41Z","timestamp":1725738881297},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_13","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"148-159","source":"Crossref","is-referenced-by-count":4,"title":["Sparse Suffix Tree Construction in Small Space"],"prefix":"10.1007","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Fischer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsvi","family":"Kopelowitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Sach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hjalte Wedel","family":"Vildh\u00f8j","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: An O(n logn) Sorting Network. In: Proc. 15th STOC, pp. 1\u20139 (1983)","DOI":"10.1145\/800061.808726"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/3-540-61258-0_9","volume-title":"Combinatorial Pattern Matching","author":"A. Andersson","year":"1996","unstructured":"Andersson, A., Larsson, N.J., Swanson, K.: Suffix Trees on Words. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 102\u2013115. Springer, Heidelberg (1996)"},{"issue":"3","key":"13_CR3","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/PL00009260","volume":"23","author":"A. Andersson","year":"1999","unstructured":"Andersson, A., Larsson, N.J., Swanson, K.: Suffix Trees on Words. Algorithmica\u00a023(3), 246\u2013260 (1999)","journal-title":"Algorithmica"},{"key":"13_CR4","unstructured":"Batcher, K.E.: Sorting Networks and Their Applications. In: Proc. AFIPS Spring JCC, pp. 307\u2013314 (1968)"},{"key":"13_CR5","unstructured":"Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: Proc. 8th SODA, pp. 360\u2013369 (1997)"},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-44888-8_5","volume-title":"Combinatorial Pattern Matching","author":"S. Burkhardt","year":"2003","unstructured":"Burkhardt, S., K\u00e4rkk\u00e4inen, J.: Fast Lightweight Suffix Array Construction and Checking. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 55\u201369. Springer, Heidelberg (2003)"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-540-73437-6_33","volume-title":"Combinatorial Pattern Matching","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Fischer, J.: Suffix Arrays on Words. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 328\u2013339. Springer, Heidelberg (2007)"},{"issue":"1","key":"13_CR8","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","volume":"16","author":"N.J. Fine","year":"1965","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness Theorems for Periodic Functions. Proc. AMS\u00a016(1), 109\u2013114 (1965)","journal-title":"Proc. AMS"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/11780441_7","volume-title":"Combinatorial Pattern Matching","author":"S. Inenaga","year":"2006","unstructured":"Inenaga, S., Takeda, M.: On-line linear-time construction of word suffix trees. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 60\u201371. Springer, Heidelberg (2006)"},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/3-540-61332-3_155","volume-title":"Computing and Combinatorics","author":"J. K\u00e4rkk\u00e4inen","year":"1996","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Sparse Suffix Trees. In: Cai, J.-Y., Wong, C.K. (eds.) COCOON 1996. LNCS, vol.\u00a01090, pp. 219\u2013230. Springer, Heidelberg (1996)"},{"issue":"2","key":"13_CR11","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient Randomized Pattern-Matching Algorithms. IBM J. Res. Dev.\u00a031(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T. Kasai","year":"2001","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 181\u2013192. Springer, Heidelberg (2001)"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Kolpakov, R., Kucherov, G., Starikovskaya, T.A.: Pattern Matching on Sparse Suffix Trees. In: Proc. 1st CCP, pp. 92\u201397 (2011)","DOI":"10.1109\/CCP.2011.45"},{"issue":"5","key":"13_CR14","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.\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"13_CR15","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D.R. Morrison","year":"1968","unstructured":"Morrison, D.R.: Patricia-practical algorithm to retrieve information coded in alphanumeric. J. ACM\u00a015(4), 514\u2013534 (1968)","journal-title":"J. ACM"},{"issue":"1","key":"13_CR16","first-page":"65","volume":"5","author":"M. Paterson","year":"1990","unstructured":"Paterson, M.: Improved Sorting Networks with O(logN) Depth. Algorithmica\u00a05(1), 65\u201392 (1990)","journal-title":"Algorithmica"},{"key":"13_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-642-21458-5_22","volume-title":"Combinatorial Pattern Matching","author":"T. Uemura","year":"2011","unstructured":"Uemura, T., Arimura, H.: Sparse and truncated suffix trees on variable-length codes. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 246\u2013260. Springer, Heidelberg (2011)"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear Pattern Matching Algorithms. In: Proc. 14th FOCS (SWAT), pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:23:15Z","timestamp":1557912195000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}