{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:00:43Z","timestamp":1725897643646},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642322402"},{"type":"electronic","value":"9783642322419"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32241-9_33","type":"book-chapter","created":{"date-parts":[[2012,8,13]],"date-time":"2012-08-13T15:12:12Z","timestamp":1344870732000},"page":"384-395","source":"Crossref","is-referenced-by-count":2,"title":["Multi-pattern Matching with Bidirectional Indexes"],"prefix":"10.1007","author":[{"given":"Simon","family":"Gog","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kalle","family":"Karhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Niko","family":"V\u00e4lim\u00e4ki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report Technical Report 124, Digital Equipment Corporation (1994)"},{"key":"33_CR2","unstructured":"Clark, D.R.: Compact pat trees. PhD thesis, Waterloo, Ont., Canada, Canada (1998)"},{"issue":"15","key":"33_CR3","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","volume":"25","author":"R. Li","year":"2009","unstructured":"Li, R., et al.: Soap2. Bioinformatics\u00a025(15), 1966\u20131967 (2009)","journal-title":"Bioinformatics"},{"issue":"4","key":"33_CR4","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed texts. Journal of the ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"Journal of the ACM"},{"issue":"2","key":"33_CR5","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J. Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput.\u00a040(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"issue":"51","key":"33_CR6","doi-asserted-by":"publisher","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","volume":"410","author":"J. Fischer","year":"2009","unstructured":"Fischer, J., M\u00e4kinen, V., Navarro, G.: Faster entropy-bounded compressed suffix trees. Theor. Comput. Sci.\u00a0410(51), 5354\u20135364 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Fischer, J., M\u00e4kinen, V., V\u00e4lim\u00e4ki, N.: Space efficient string mining under frequency constraints. In: ICDM, pp. 193\u2013202 (2008)","DOI":"10.1109\/ICDM.2008.32"},{"key":"33_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-642-29344-3_34","volume-title":"LATIN 2012: Theoretical Informatics","author":"T. Gagie","year":"2012","unstructured":"Gagie, T., Karhu, K., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V., Salmela, L., Tarhio, J.: Indexed Multi-pattern Matching. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 399\u2013407. Springer, Heidelberg (2012)"},{"key":"33_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-03784-9_1","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2009","unstructured":"Gagie, T., Puglisi, S.J., Turpin, A.: Range Quantile Queries: Another Virtue of Wavelet Trees. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 1\u20136. Springer, Heidelberg (2009)"},{"key":"33_CR10","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S1074-5521(98)90108-9","volume":"5","author":"J. Handelsman","year":"1998","unstructured":"Handelsman, J., Rondon, M.R., Brady, S.F., Clardy, J., Goodman, R.: Molecular biological access to the chemistry of unknown soil microbes: a new frontier for natural products. Chemistry & Biology\u00a05, 245\u2013249 (1998)","journal-title":"Chemistry & Biology"},{"key":"33_CR11","first-page":"230","volume-title":"Proc. 3rd Annual Symposium on Combinatorial Pattern Matching","author":"L.C.K. Hui","year":"1992","unstructured":"Hui, L.C.K.: Color set size problem with application to string matching. In: Proc. 3rd Annual Symposium on Combinatorial Pattern Matching, pp. 230\u2013243. Springer, London (1992)"},{"key":"33_CR12","unstructured":"Jacobson, G.: Succinct Static Data Structures. PhD thesis. Carnegie\u2013Mellon University, CMU-CS-89-112 (1989)"},{"key":"33_CR13","first-page":"226","volume-title":"Proceedings of the Prague Stringology Conference 2011","author":"K. Karhu","year":"2011","unstructured":"Karhu, K.: Improving exact search of multiple patterns from a compressed suffix array. In: Holub, J., \u017d\u010f\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference 2011, pp. 226\u2013231. Czech Technical University in Prague, Czech Republic (2011)"},{"key":"33_CR14","unstructured":"Karhu, K., M\u00e4kinen, V.: Practical multi-pattern matching with bidirectional indexes. Submitted manuscript (2012)"},{"key":"33_CR15","doi-asserted-by":"crossref","unstructured":"Lam, T.W., Li, R., Tam, A., Wong, S., Wu, E., Yiu, S.M.: High throughput short read alignment via bi-directional BWT. In: IEEE International Conference on Bioinformatics and Biomedicine, vol.\u00a00, pp. 31\u201336 (2009)","DOI":"10.1109\/BIBM.2009.42"},{"key":"33_CR16","doi-asserted-by":"crossref","unstructured":"Langmead, B., Trapnell, C., Pop, M., Salzberg, S.L.: Ultrafast and memory-efficient alignment of short dna sequences to the human genome. Genome Biology\u00a010(3), R25 (2009)","DOI":"10.1186\/gb-2009-10-3-r25"},{"issue":"14","key":"33_CR17","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","volume":"25","author":"H. Li","year":"2009","unstructured":"Li, H., Durbin, R.: Fast and accurate short read alignment with burrows-wheeler transform. Bioinformatics\u00a025(14), 1754\u20131760 (2009)","journal-title":"Bioinformatics"},{"issue":"1","key":"33_CR18","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00453-003-1029-2","volume":"37","author":"M.G. Maa\u00df","year":"2003","unstructured":"Maa\u00df, M.G.: Linear bidirectional on-line construction of affix trees. Algorithmica\u00a037(1), 43\u201374 (2003)","journal-title":"Algorithmica"},{"key":"33_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-12476-1_13","volume-title":"Algorithms and Applications","author":"V. M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., V\u00e4lim\u00e4ki, N., Laaksonen, A., Katainen, R.: Unified View of Backward Backtracking in Short Read Mapping. In: Elomaa, T., Mannila, H., Orponen, P. (eds.) Ukkonen Festschrift 2010. LNCS, vol.\u00a06060, pp. 182\u2013195. Springer, Heidelberg (2010)"},{"key":"33_CR20","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys\u00a039(1), article 2 (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"33_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2000807.2000821","volume":"7","author":"L.M.S. Russo","year":"2011","unstructured":"Russo, L.M.S., Navarro, G., Oliveira, A.L.: Fully compressed suffix trees. ACM Trans. Algorithms\u00a07, 53:1\u201353:34 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"33_CR22","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theor. Comp. Sys.\u00a041, 589\u2013607 (2007)","journal-title":"Theor. Comp. Sys."},{"key":"33_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-13509-5_5","volume-title":"Combinatorial Pattern Matching","author":"T. Schnattinger","year":"2010","unstructured":"Schnattinger, T., Ohlebusch, E., Gog, S.: Bidirectional Search in a String with Wavelet Trees. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 40\u201350. Springer, Heidelberg (2010)"},{"key":"33_CR24","unstructured":"Stoye, J.: Affix trees. Technical Report 2000-04, Faculty of Technology, Bielefeld University (2000), \n                  \n                    http:\/\/www.techfak.uni-bielefeld.de\/~stoye\/rpublications\/report00-04.pdf"},{"key":"33_CR25","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer (2001)"},{"key":"33_CR26","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32241-9_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:58:55Z","timestamp":1620129535000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32241-9_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642322402","9783642322419"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32241-9_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}