{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:31:03Z","timestamp":1725456663078},"publisher-location":"Berlin\/Heidelberg","reference-count":10,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354056764X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029793","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T04:36:08Z","timestamp":1133411768000},"page":"11-19","source":"Crossref","is-referenced-by-count":3,"title":["Tight comparison bounds for the string prefix-matching problem"],"prefix":"10.1007","author":[{"given":"Dany","family":"Breslauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Livio","family":"Colussi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laura","family":"Toniolo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974."},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R. S. Boyer","year":"1977","unstructured":"R. S. Boyer and J. S. Moore. A fast string searching algorithm. Comm. of the ACM, 20:762\u2013772, 1977.","journal-title":"Comm. of the ACM"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"D. Breslauer, L. Colussi, and L. Toniolo. On the Exact Complexity of the String Prefix-Matching Problem. In preparation, 1993.","DOI":"10.21236\/ADA267758"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"D. Breslauer and Z. Galil. Efficient Comparison Based String Matching. J. Complexity, 1993. To appear.","DOI":"10.1006\/jcom.1993.1022"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"R. Cole and R. Hariharan. Tighter Bounds on The Exact Complexity of String Matching. In Proc. 33rd IEEE Symp. on Foundations of Computer Science, pages 600\u2013609, 1992.","DOI":"10.1109\/SFCS.1992.267791"},{"key":"2_CR6","first-page":"225","volume":"95","author":"L. Colussi","year":"1991","unstructured":"L. Colussi. Correctness and efficiency of string matching algorithms. Inform. and Control, 95:225\u2013251, 1991.","journal-title":"Inform. and Control"},{"issue":"6","key":"2_CR7","doi-asserted-by":"crossref","first-page":"1008","DOI":"10.1137\/0220063","volume":"20","author":"Z. Galil","year":"1991","unstructured":"Z. Galil and R. Giancarlo. On the exact complexity of string matching: lower bounds. SIAM J. Comput., 20(6):1008\u20131020, 1991.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2_CR8","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1137\/0221028","volume":"21","author":"Z. Galil","year":"1992","unstructured":"Z. Galil and R. Giancarlo. The exact complexity of string matching: upper bounds. SIAM J. Comput., 21(3):407\u2013437, 1992.","journal-title":"SIAM J. Comput."},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1137\/0206024","volume":"6","author":"D. E. Knuth","year":"1977","unstructured":"D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6:322\u2013350, 1977.","journal-title":"SIAM J. Comput."},{"key":"2_CR10","unstructured":"U. Zwick and M. S. Paterson. Lower bounds for string matching in the sequential comparison model. Manuscript, 1991."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029793","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T04:34:02Z","timestamp":1586579642000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029793"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354056764X"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/bfb0029793","relation":{},"subject":[]}}