{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T22:06:49Z","timestamp":1768255609682,"version":"3.49.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4-5","license":[{"start":{"date-parts":[[1994,11,1]],"date-time":"1994-11-01T00:00:00Z","timestamp":783648000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,11]]},"DOI":"10.1007\/bf01185428","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T16:12:30Z","timestamp":1108743150000},"page":"268-292","source":"Crossref","is-referenced-by-count":8,"title":["On Boyer-Moore automata"],"prefix":"10.1007","volume":"12","author":[{"given":"R. A.","family":"Baeza-Yates","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Choffrut","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G. H.","family":"Gonnet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01185428_CR1","first-page":"255","volume-title":"Handbook of Theoretical Computer Science, volume A","author":"A. V. Aho","year":"1990","unstructured":"A. V. Aho. Algorithms for finding patterns in strings. In Janvan Leeuwen, editor,Handbook of Theoretical Computer Science, volume A, pages 255\u2013300. Elsevier, Amsterdam, 1990."},{"key":"BF01185428_CR2","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1137\/0215007","volume":"15","author":"A. Apostolico","year":"1986","unstructured":"A. Apostolico and R. Giancarlo. The Boyer-Moore-Galil string searching strategies revisited.SIAM J. Comput., 15:98\u2013105, 1986.","journal-title":"SIAM J. Comput."},{"key":"BF01185428_CR3","unstructured":"V. Bruy\u00e8re. Th\u00e8se annexe, automates de Boyer-Moore. Technical Report, Institut de Math\u00e9matique et d'Informatique, Universit\u00e9 de Mons-hainaut, 1991."},{"key":"BF01185428_CR4","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R. Boyer","year":"1977","unstructured":"R. Boyer and S. Moore. A fast string searching algorithm.Comm. ACM, 20:762\u2013772, 1977.","journal-title":"Comm. ACM"},{"key":"BF01185428_CR5","unstructured":"R. A. Baeza-Yates. Efficient Text Searching. Ph.D. thesis, Dept. of Computer Science, University of Waterloo, May 1989. Also as Research Report CS-89-17."},{"key":"BF01185428_CR6","first-page":"75","volume-title":"Lecture Notes on Computer Science, Vol. 382","author":"R. A. Baeza-Yates","year":"1989","unstructured":"R. A. Baeza-Yates. String searching algorithms revisited. In F. Dehne, J.-R. Sack, and N. Santoro, editors,Proceedings of the Workshop in Algorithms and Data Structures, pages 75\u201396, Ottawa, Canada, August 1989. Lecture Notes on Computer Science, Vol. 382. Springer-Verlag, Berlin, 1989."},{"key":"BF01185428_CR7","unstructured":"R. Baeza-Yates, G. Gonnet, and M. R\u00e9gnier. Analysis of Boyer-Moore-type string searching algorithms.Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms, pages 328\u2013343, San Francisco, January 1990."},{"issue":"1","key":"BF01185428_CR8","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0304-3975(92)90133-Z","volume":"92","author":"R. Baeza-Yates","year":"1992","unstructured":"R. Baeza-Yates and M. R\u00e9gnier. Average running time of the Boyer-Moore-Horspool algorithm.Theoret. Comput. Sci., 92(1):19\u201331, 1992.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01185428_CR9","first-page":"217","volume":"40","author":"C. Choffrut","year":"1990","unstructured":"C. Choffrut. An optimal algorithm for building the Boyer-Moore automaton.Bull. EATCS, 40:217\u2013224, 1990.","journal-title":"Bull. EATCS"},{"key":"BF01185428_CR10","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1145\/359146.359148","volume":"22","author":"Z. Galil","year":"1979","unstructured":"Z. Galil. On improving the worst case running time of the Boyer-Moore string matching algorithm.Comm. ACM, 22:505\u2013508, 1979.","journal-title":"Comm. ACM"},{"key":"BF01185428_CR11","series-title":"NATO ASI Series","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-82456-2_1","volume-title":"Combinatorial Algorithms on Words","author":"Z. Galil","year":"1985","unstructured":"Z. Galil. Open problems in stringology. In A. Apostolico and Z. Galil, editors,Combinatorial Algorithms on Words. NATO ASI Series, volume F12, pages 1\u20138. Springer-Verlag, Berlin, 1985."},{"key":"BF01185428_CR12","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1137\/0209051","volume":"9","author":"L. Guibas","year":"1980","unstructured":"L. Guibas and A. Odlyzko. A new proof of the linearity of the Boyer-Moore string searching algorithm.SIAM J. Comput., 9:672\u2013682, 1980.","journal-title":"SIAM J. Comput."},{"key":"BF01185428_CR13","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1002\/spe.4380100608","volume":"10","author":"R. N. Horspool","year":"1980","unstructured":"R. N. Horspool. Practical fast searching in strings.Software\u2014Practice and Experience, 10:501\u2013506, 1980.","journal-title":"Software\u2014Practice and Experience"},{"key":"BF01185428_CR14","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D. E. Knuth","year":"1977","unstructured":"D. E. Knuth, J. Morris, and V. Pratt. Fast pattern matching in strings.SIAM J. Comput., 6:323\u2013350, 1977.","journal-title":"SIAM J. Comput."},{"key":"BF01185428_CR15","volume-title":"Finite Markov Chains","author":"J. G. Kemeny","year":"1983","unstructured":"J. G. Kemeny and J. L. Snell.Finite Markov Chains. Springer-Verlag, New York, 1983."},{"key":"BF01185428_CR16","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1137\/0206048","volume":"6","author":"R. Rivest","year":"1977","unstructured":"R. Rivest. On the worst-case behavior of string-searching algorithms.SIAM J. Comput., 6:669\u2013674, 1977.","journal-title":"SIAM J. Comput."},{"key":"BF01185428_CR17","unstructured":"R. Scheihing. Personal communication, 1992."},{"key":"BF01185428_CR18","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1137\/0208029","volume":"8","author":"A. C. Yao","year":"1979","unstructured":"A. C. Yao. The complexity of pattern matching for a random string.SIAM J. Comput., 8:368\u2013387, 1979.","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185428.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01185428\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185428","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T16:41:38Z","timestamp":1556728898000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01185428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,11]]},"references-count":18,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[1994,11]]}},"alternative-id":["BF01185428"],"URL":"https:\/\/doi.org\/10.1007\/bf01185428","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,11]]}}}