{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T13:32:41Z","timestamp":1742391161061},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642130885"},{"type":"electronic","value":"9783642130892"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13089-2_37","type":"book-chapter","created":{"date-parts":[[2010,5,7]],"date-time":"2010-05-07T12:05:27Z","timestamp":1273233927000},"page":"439-450","source":"Crossref","is-referenced-by-count":1,"title":["Exact Analysis of Horspool\u2019s and Sunday\u2019s Pattern Matching Algorithms with Probabilistic Arithmetic Automata"],"prefix":"10.1007","author":[{"given":"Tobias","family":"Marschall","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"Rahmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"37_CR1","first-page":"328","volume-title":"SODA \u201990: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms","author":"R.A. Baeza-Yates","year":"1990","unstructured":"Baeza-Yates, R.A., Gonnet, G.H., R\u00e9gnier, M.: Analysis of Boyer-Moore-type string searching algorithms. In: SODA \u201990: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, pp. 328\u2013343. SIAM, Philadelphia (1990)"},{"issue":"1","key":"37_CR2","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0304-3975(92)90133-Z","volume":"92","author":"R.A. Baeza-Yates","year":"1992","unstructured":"Baeza-Yates, R.A., R\u00e9gnier, M.: Average running time of the Boyer-Moore-Horspool algorithm. Theor. Comput. Sci.\u00a092(1), 19\u201331 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"10","key":"37_CR3","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R.S. Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Communications of the ACM\u00a020(10), 762\u2013772 (1977)","journal-title":"Communications of the ACM"},{"key":"37_CR4","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-540-87361-7_27","volume-title":"Algorithms in Bioinformatics","author":"I. Herms","year":"2008","unstructured":"Herms, I., Rahmann, S.: Computing alignment seed sensitivity with probabilistic arithmetic automata. In: Crandall, K.A., Lagergren, J. (eds.) WABI 2008. LNCS (LNBI), vol.\u00a05251, pp. 318\u2013329. Springer, Heidelberg (2008)"},{"key":"37_CR5","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1002\/spe.4380100608","volume":"10","author":"R.N. Horspool","year":"1980","unstructured":"Horspool, R.N.: Practical fast searching in strings. Software-Practice and Experience\u00a010, 501\u2013506 (1980)","journal-title":"Software-Practice and Experience"},{"issue":"2","key":"37_CR6","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J., Pratt, V.R.: Fast pattern matching in strings. SIAM Journal on Computing\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"37_CR7","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1142\/S0219720006001977","volume":"4","author":"G. Kucherov","year":"2006","unstructured":"Kucherov, G., No\u00e9, L., Roytberg, M.: A unifying framework for seed sensitivity and its application to subset seeds. Journal of Bioinformatics and Computational Biology\u00a04(2), 553\u2013569 (2006)","journal-title":"Journal of Bioinformatics and Computational Biology"},{"issue":"1-2","key":"37_CR8","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<169::AID-RSA9>3.0.CO;2-T","volume":"10","author":"H.M. Mahmoud","year":"1997","unstructured":"Mahmoud, H.M., Smythe, R.T., R\u00e9gnier, M.: Analysis of Boyer-Moore-Horspool string-matching heuristic. Random Structures and Algorithms\u00a010(1-2), 169\u2013186 (1997)","journal-title":"Random Structures and Algorithms"},{"key":"37_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-540-69068-9_11","volume-title":"Combinatorial Pattern Matching","author":"T. Marschall","year":"2008","unstructured":"Marschall, T., Rahmann, S.: Probabilistic arithmetic automata and their application to pattern matching statistics. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 95\u2013106. Springer, Heidelberg (2008)"},{"issue":"12","key":"37_CR10","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1093\/bioinformatics\/btp188","volume":"25","author":"T. Marschall","year":"2009","unstructured":"Marschall, T., Rahmann, S.: Efficient exact motif discovery. Bioinformatics\u00a025(12), i356\u2013i364 (2009)","journal-title":"Bioinformatics"},{"key":"37_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316135228","volume-title":"Flexible Pattern Matching in Strings","author":"G. Navarro","year":"2002","unstructured":"Navarro, G., Raffinot, M.: Flexible Pattern Matching in Strings. Cambridge University Press, Cambridge (2002)"},{"key":"37_CR12","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-540-87361-7_26","volume-title":"Algorithms in Bioinformatics","author":"M. Schulz","year":"2008","unstructured":"Schulz, M., Weese, D., Rausch, T., D\u00f6ring, A., Reinert, K., Vingron, M.: Fast and adaptive variable order Markov chain construction. In: Crandall, K.A., Lagergren, J. (eds.) WABI 2008. LNCS (LNBI), vol.\u00a05251, pp. 306\u2013317. Springer, Heidelberg (2008)"},{"issue":"2","key":"37_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1002\/1098-2418(200103)18:2<153::AID-RSA1003>3.0.CO;2-O","volume":"18","author":"R.T. Smythe","year":"2001","unstructured":"Smythe, R.T.: The Boyer-Moore-Horspool heuristic with Markovian input. Random Structures and Algorithms\u00a018(2), 153\u2013163 (2001)","journal-title":"Random Structures and Algorithms"},{"issue":"8","key":"37_CR14","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1145\/79173.79184","volume":"33","author":"D.M. Sunday","year":"1990","unstructured":"Sunday, D.M.: A very fast substring search algorithm. Communications of the ACM\u00a033(8), 132\u2013142 (1990)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13089-2_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T11:54:38Z","timestamp":1619783678000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13089-2_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130885","9783642130892"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13089-2_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}