{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:45:51Z","timestamp":1725795951231},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319075655"},{"type":"electronic","value":"9783319075662"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07566-2_25","type":"book-chapter","created":{"date-parts":[[2014,6,12]],"date-time":"2014-06-12T03:50:31Z","timestamp":1402545031000},"page":"242-251","source":"Crossref","is-referenced-by-count":2,"title":["On Hardness of Several String Indexing Problems"],"prefix":"10.1007","author":[{"given":"Kasper Green","family":"Larsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper Sindahl","family":"Nielsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"25_CR1","doi-asserted-by":"publisher","first-page":"69","DOI":"10.4086\/toc.2012.v008a004","volume":"8","author":"N. Bansal","year":"2012","unstructured":"Bansal, N., Williams, R.: Regularity lemmas and combinatorial algorithms. Theory of Computing\u00a08(1), 69\u201394 (2012)","journal-title":"Theory of Computing"},{"issue":"4","key":"25_CR2","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1007\/s00453-011-9499-0","volume":"63","author":"G.S. Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica\u00a063(4), 815\u2013830 (2012)","journal-title":"Algorithmica"},{"key":"25_CR3","unstructured":"Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. In: STACS. LIPIcs, vol.\u00a014, pp. 290\u2013301. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-31155-0_26","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"T.M. Chan","year":"2012","unstructured":"Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T.: Linear-space data structures for range minority query in arrays. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 295\u2013306. Springer, Heidelberg (2012)"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., Patrascu, M.: Orthogonal range searching on the ram, revisited. In: Symposium on Computational Geometry, pp. 1\u201310. ACM (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"40-42","key":"25_CR6","doi-asserted-by":"publisher","first-page":"3795","DOI":"10.1016\/j.tcs.2010.06.002","volume":"411","author":"H. Cohen","year":"2010","unstructured":"Cohen, H., Porat, E.: Fast set intersection and two-patterns matching. Theor. Comput. Sci.\u00a0411(40-42), 3795\u20133800 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"25_CR7","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1016\/S0022-0000(03)00028-X","volume":"66","author":"P. Ferragina","year":"2003","unstructured":"Ferragina, P., Koudas, N., Muthukrishnan, S., Srivastava, D.: Two-dimensional substring indexing. J. Comput. Syst. Sci.\u00a066(4), 763\u2013774 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-642-29344-3_28","volume-title":"LATIN 2012: Theoretical Informatics","author":"J. Fischer","year":"2012","unstructured":"Fischer, J., Gagie, T., Kopelowitz, T., Lewenstein, M., M\u00e4kinen, V., Salmela, L., V\u00e4lim\u00e4ki, N.: Forbidden patterns. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 327\u2013337. Springer, Heidelberg (2012)"},{"key":"25_CR9","unstructured":"Gall, F.L.: Powers of tensors and fast matrix multiplication. CoRR, abs\/1401.7714 (2014)"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rankselect operations on large alphabets: A tool for text indexing. In: SODA, pp. 368\u2013373. ACM Press (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-16321-0_6","volume-title":"String Processing and Information Retrieval","author":"W.-K. Hon","year":"2010","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: String retrieval for multi-pattern queries. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 55\u201366. Springer, Heidelberg (2010)"},{"key":"25_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-642-31265-6_15","volume-title":"Combinatorial Pattern Matching","author":"W.-K. Hon","year":"2012","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: Document listing for queries with excluded pattern. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 185\u2013195. Springer, Heidelberg (2012)"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: Space-efficient framework for top-k string retrieval. In: JACM (2014)","DOI":"10.1145\/2590774"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1007\/978-3-540-30551-4_49","volume-title":"Algorithms and Computation","author":"J. J\u00e1J\u00e1","year":"2004","unstructured":"J\u00e1J\u00e1, J., Mortensen, C.W., Shi, Q.: Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 558\u2013568. Springer, Heidelberg (2004)"},{"key":"25_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/3-540-68530-8_6","volume-title":"Algorithms - ESA \u201998","author":"Y. Matias","year":"1998","unstructured":"Matias, Y., Muthukrishnan, S.M., \u015eahinalp, S.C., Ziv, J.: Augmenting suffix trees, with applications. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 67\u201378. Springer, Heidelberg (1998)"},{"key":"25_CR16","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: SODA, pp. 657\u2013666. ACM\/SIAM (2002)"},{"key":"25_CR17","unstructured":"Navarro, G.: Spaces, trees and colors: The algorithmic landscape of document retrieval on sequences. CoRR, abs\/1304.6023 (2013)"},{"key":"25_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-642-31155-0_24","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"Y. Nekrich","year":"2012","unstructured":"Nekrich, Y., Navarro, G.: Sorted range reporting. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 271\u2013282. Springer, Heidelberg (2012)"}],"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-07566-2_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:32:55Z","timestamp":1558924375000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07566-2_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319075655","9783319075662"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07566-2_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}