{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T23:40:25Z","timestamp":1736293225650,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540584346"},{"type":"electronic","value":"9783540487944"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/bfb0049433","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T18:42:35Z","timestamp":1141670555000},"page":"483-494","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the exact complexity of 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","published-online":{"date-parts":[[2006,2,23]]},"reference":[{"key":"43_CR1","doi-asserted-by":"publisher","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":"43_CR2","doi-asserted-by":"crossref","unstructured":"D. Breslauer. Fast Parallel String Prefix-Matching. Technical Report CUCS-041-92, Computer Science Dept., Columbia University, 1992.","DOI":"10.21236\/ADA267758"},{"issue":"1","key":"43_CR3","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0020-0190(93)90156-4","volume":"47","author":"D. Breslauer","year":"1993","unstructured":"D. Breslauer, L. Colussi, and L. Toniolo. Tight Comparison Bounds for the String Prefix-Matching Problem. Inform. Process. Lett., 47(1):51\u201357, 1993.","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"43_CR4","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1006\/jcom.1993.1022","volume":"9","author":"D. Breslauer","year":"1993","unstructured":"D. Breslauer and Z. Galil. Efficient Comparison Based String Matching. J. Complexity, 9(3):339\u2013365, 1993.","journal-title":"J. Complexity"},{"key":"43_CR5","doi-asserted-by":"crossref","unstructured":"R. Cole, M. Crochemore, Z. Galil, L. Gasieniec, R. Hariharan, S. Muthukrishnan, K. Park, and W. Rytter. Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. In Proc. 34th IEEE Symp. on Foundations of Computer Science, pages 248\u2013258, 1993.","DOI":"10.1109\/SFCS.1993.366862"},{"key":"43_CR6","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":"43_CR7","doi-asserted-by":"crossref","unstructured":"R. Cole, R. Hariharan, M.S. Paterson, and U. Zwick. Which patterns are hard to find. In Proc. 2nd Israeli Symp. on Theory of Computing and Systems, pages 59\u201368, 1993.","DOI":"10.1109\/ISTCS.1993.253483"},{"key":"43_CR8","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"},{"key":"43_CR9","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/S0019-9958(85)80031-0","volume":"67","author":"Z. Galil","year":"1985","unstructured":"Z. Galil. Optimal parallel algorithms for string matching. Inform. and Control, 67:144\u2013157, 1985.","journal-title":"Inform. and Control"},{"issue":"6","key":"43_CR10","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":"43_CR11","doi-asserted-by":"publisher","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":"43_CR12","doi-asserted-by":"crossref","unstructured":"Z. Galil and K. Park. Truly Alphabet-Independent Two-Dimensional Pattern Matching. In Proc. 33th IEEE Symp. on Foundations of Computer Science, pages 247\u2013256, 1992.","DOI":"10.1109\/SFCS.1992.267767"},{"key":"43_CR13","unstructured":"L. Gasieniec and K. Park. Fully Optimal Parallel Prefix Matching. This conference proceedings."},{"issue":"2","key":"43_CR14","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0190(93)90231-W","volume":"47","author":"C. Hancart","year":"1993","unstructured":"C. Hancart. On Simon's string searching algorithm. Inform. Process. Lett., 47(2):95\u201399, 1993.","journal-title":"Inform. Process. Lett."},{"key":"43_CR15","unstructured":"R. Hariharan and S. Muthukrishnan. Optimal Parallel Algorithms for Prefix Matching. In Proc. 21th International Colloquium on Automata, Languages, and Programming. To appear."},{"key":"43_CR16","doi-asserted-by":"publisher","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":"43_CR17","volume-title":"Combinatorics on Words","author":"M. Lothaire","year":"1983","unstructured":"M. Lothaire. Combinatorics on Words. Addison-Wesley, Reading, MA., U.S.A., 1983."},{"key":"43_CR18","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"G.M. Main","year":"1984","unstructured":"G.M. Main and R.J. Lorentz. An O(n log n) algorithm for finding all repetitions in a string. J. Algorithms, 5:422\u2013432, 1984.","journal-title":"J. Algorithms"},{"key":"43_CR19","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1137\/0206048","volume":"6","author":"R.V. Rivest","year":"1977","unstructured":"R.V. Rivest. On the Worst Case Behavior of String-Searching Algorithms. SIAM J. Comput., 6:669\u2013674, 1977.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T22:59:55Z","timestamp":1736290795000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049433"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584346","9783540487944"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0049433","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"23 February 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}