{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:33:10Z","timestamp":1725485590128},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540651420"},{"type":"electronic","value":"9783540495437"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49543-6_16","type":"book-chapter","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T02:58:05Z","timestamp":1181185085000},"page":"187-199","source":"Crossref","is-referenced-by-count":3,"title":["Complexity of Sequential Pattern Matching Algorithms"],"prefix":"10.1007","author":[{"given":"Mireille","family":"R\u00e9gnier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,6,11]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","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. Compt., 15, 98\u2013105, 1986.","journal-title":"SIAM J. Compt."},{"key":"16_CR2","doi-asserted-by":"publisher","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 Boyer-Moore-Horspool Algorithm, Theoretical Computer Science, 92, 19\u201331, 1992.","journal-title":"Theoretical Computer Science"},{"key":"16_CR3","volume-title":"Convergence of Probability Measures","author":"P. Billingsley","year":"1968","unstructured":"P. Billingsley, Convergence of Probability Measures, John Wiley & Sons, New York, 1968."},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0166-218X(92)90270-K","volume":"24","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht and D. Haussler, Average Size of Suffix Trees and DAWGS, Discrete Applied Mathematics, 24, 37\u201345, 1989.","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R. Boyer","year":"1977","unstructured":"R. Boyer and J. Moore, A fast String Searching Algorithm, Comm. of the ACM, 20, 762\u2013772, 1977.","journal-title":"Comm. of the ACM"},{"doi-asserted-by":"crossref","unstructured":"D. Breslauer, L. Colussi, and L. Toniolo, Tight Comparison Bounds for the String Prefix-Matching Problem, Proc. 4-th Symposium on Combinatorial Pattern Matching, Padova, Italy, 11\u201319. Springer-Verlag, 1993.","key":"16_CR6","DOI":"10.1007\/BFb0029793"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/S0097539793245829","volume":"24","author":"R. Cole","year":"1995","unstructured":"R. Cole, R. Hariharan, M. Paterson, and U. Zwick, Tighter Lower Bounds on the Exact Complexity of String Matching, SIAM J. Comp., 24, 30\u201345, 1995.","journal-title":"SIAM J. Comp."},{"doi-asserted-by":"crossref","unstructured":"L. Colussi, Z. Galil, and R. Giancarlo, On the Exact Complexity of String Matching, Proc. 31-st Annual IEEE Symposium on the Foundations of Computer Science, 135\u2013143. IEEE, 1990.","key":"16_CR8","DOI":"10.1109\/FSCS.1990.89532"},{"key":"16_CR9","volume-title":"Text Algorithms","author":"M. Crochemore","year":"1995","unstructured":"M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York 1995."},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1214\/aop\/1176993511","volume":"11","author":"Y. Derriennic","year":"1983","unstructured":"Y. Derriennic, Une Th\u00e9or\u00e9me Ergodique Presque Sous Additif, Ann. Probab., 11, 669\u2013677, 1983.","journal-title":"Ann. Probab."},{"key":"16_CR11","volume-title":"Probability: Theory and Examples","author":"R. Durrett","year":"1991","unstructured":"R. Durrett, Probability: Theory and Examples, Wadsworth & Brooks\/Cole Books, Pacific Grove, California, 1991."},{"key":"16_CR12","doi-asserted-by":"publisher","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 Matching Algorithm, SIAM J. Compt., 9, 672\u2013682, 1980.","journal-title":"SIAM J. Compt."},{"unstructured":"C. Hancart, Analyse Exacte et en Moyenne d\u2019Algorithmes de Recherche d\u2019un Motif dans un Texte, These, l\u2019Universite Paris 7, 1993.","key":"16_CR13"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0097-3165(94)90065-5","volume":"66","author":"P. Jacquet","year":"1994","unstructured":"P. Jacquet and W. Szpankowski, Autocorrelation on Words and Its Applications. Analysis of Suffix Tree by String-Ruler Approach, J. Combinatorial Theory. Ser. A, 66, 237\u2013269, 1994.","journal-title":"J. Combinatorial Theory. Ser. A"},{"key":"16_CR15","series-title":"Lecture Notes in Mathematics","volume-title":"Subadditive Processes","author":"J.F.C. Kingman","year":"1976","unstructured":"J.F.C. Kingman, Subadditive Processes, in Ecole d\u2019Et\u00e9 de Probabilit\u00e9s de Saint-Flour V-1975, Lecture Notes in Mathematics, 539, Springer-Verlag, Berlin 1976."},{"key":"16_CR16","first-page":"189","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"D.E. Knuth, J. Morris and V. Pratt, Fast Pattern Matching in Strings, SIAM J. Compt., 6, 189\u2013195, 1977.","journal-title":"SIAM J. Compt."},{"key":"16_CR17","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. Mahmoud","year":"1996","unstructured":"H. Mahmoud, M. R\u00e9gnier and R. Smythe, Analysis of Boyer-Moore-Horspool String Matching Heuristic, in Random Structures and Algorithms, 10, 169\u2013186, 1996.","journal-title":"Random Structures and Algorithms"},{"key":"16_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/3-540-51486-4_90","volume-title":"Proc. Mathematical Foundations for Computer Science 89","author":"M. R\u00e9gnier","year":"1989","unstructured":"M. R\u00e9gnier, Knuth-Morris-Pratt Algorithm: An Analysis, Proc. Mathematical Foundations for Computer Science 89, Porubka, Poland, Lecture Notes in Computer Science, 379, 431\u2013444. Springer-Verlag, 1989."},{"unstructured":"I. Simon, String Matching Algorithms and Automata, First South-American Work-shop on String Processing 93, Belo Horizonte, Brazil, R. Baeza-Yates and N. Ziviani, ed, 151\u2013157, 1993.","key":"16_CR19"},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"1647","DOI":"10.1109\/18.259648","volume":"39","author":"W. Szpankowski","year":"1993","unstructured":"W. Szpankowski, Asymptotic Properties of Data Compression and Suffix Trees, IEEE Trans. Information Theory, 39, 1647\u20131659, 1993.","journal-title":"IEEE Trans. Information Theory"},{"key":"16_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to Computational Biology","author":"M. Waterman","year":"1995","unstructured":"M. Waterman, Introduction to Computational Biology, Chapman & Hall, London 1995."}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49543-6_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T06:02:35Z","timestamp":1550383355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49543-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651420","9783540495437"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-49543-6_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}