{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T23:10:18Z","timestamp":1743376218494,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642312649"},{"type":"electronic","value":"9783642312656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31265-6_8","type":"book-chapter","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T03:28:23Z","timestamp":1339471703000},"page":"97-109","source":"Crossref","is-referenced-by-count":1,"title":["Pattern Matching in Multiple Streams"],"prefix":"10.1007","author":[{"given":"Rapha\u00ebl","family":"Clifford","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Jalsenius","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Sach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"8_CR1","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K. Abrahamson","year":"1987","unstructured":"Abrahamson, K.: Generalized string matching. SIAM Journal on Computing\u00a016(6), 1039\u20131051 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Sokol, D.: Dynamic text and static pattern matching. ACM Transactions on Algorithms (TALG)\u00a03(2) (2007)","DOI":"10.1145\/1240233.1240242"},{"issue":"2","key":"8_CR3","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00097-X","volume":"50","author":"A. Amir","year":"2004","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. Journal of Algorithms\u00a050(2), 257\u2013275 (2004)","journal-title":"Journal of Algorithms"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-642-21458-5_15","volume-title":"Combinatorial Pattern Matching","author":"D. Breslauer","year":"2011","unstructured":"Breslauer, D., Galil, Z.: Real-Time Streaming String-Matching. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 162\u2013172. Springer, Heidelberg (2011)"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-540-69068-9_15","volume-title":"Combinatorial Pattern Matching","author":"R. Clifford","year":"2008","unstructured":"Clifford, R., Efremenko, K., Porat, B., Porat, E.: A Black Box for Online Approximate Pattern Matching. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 143\u2013151. Springer, Heidelberg (2008)"},{"issue":"4","key":"8_CR6","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1016\/j.ic.2010.12.007","volume":"209","author":"R. Clifford","year":"2011","unstructured":"Clifford, R., Efremenko, K., Porat, B., Porat, E.: A black box for online approximate pattern matching. Information and Computation\u00a0209(4), 731\u2013736 (2011)","journal-title":"Information and Computation"},{"key":"8_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-642-21458-5_17","volume-title":"Combinatorial Pattern Matching","author":"R. Clifford","year":"2011","unstructured":"Clifford, R., Jalsenius, M., Porat, E., Sach, B.: Space Lower Bounds for Online Pattern Matching. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 184\u2013196. Springer, Heidelberg (2011)"},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-642-13509-5_10","volume-title":"Combinatorial Pattern Matching","author":"R. Clifford","year":"2010","unstructured":"Clifford, R., Sach, B.: Pseudo-realtime Pattern Matching: Closing the Gap. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 101\u2013111. Springer, Heidelberg (2010)"},{"issue":"1","key":"8_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.jda.2010.09.005","volume":"9","author":"R. Clifford","year":"2011","unstructured":"Clifford, R., Sach, B.: Pattern matching in pseudo real-time. Journal of Discrete Algorithms\u00a09(1), 67\u201381 (2011)","journal-title":"Journal of Discrete Algorithms"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/978-3-642-15369-3_41","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"F. Ergun","year":"2010","unstructured":"Ergun, F., Jowhari, H., Sa\u011flam, M.: Periodicity in Streams. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010, LNCS, vol.\u00a06302, pp. 545\u2013559. Springer, Heidelberg (2010)"},{"issue":"1","key":"8_CR11","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1145\/322234.322244","volume":"28","author":"Z. Galil","year":"1981","unstructured":"Galil, Z.: String matching in real time. Journal of the ACM\u00a028(1), 134\u2013149 (1981)","journal-title":"Journal of the ACM"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Faster algorithms for string matching problems: Matching the convolution bound. In: FOCS 1998: Proc. 39th Annual Symp. Foundations of Computer Science, pp. 166\u2013173 (1998)","DOI":"10.1109\/SFCS.1998.743440"},{"issue":"1","key":"8_CR13","doi-asserted-by":"publisher","first-page":"129","DOI":"10.4086\/toc.2008.v004a006","volume":"4","author":"T.S. Jayram","year":"2008","unstructured":"Jayram, T.S., Kumar, R., Sivakumar, D.: The one-way communication complexity of hamming distance. Theory of Computing\u00a04(1), 129\u2013135 (2008)","journal-title":"Theory of Computing"},{"issue":"2","key":"8_CR14","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(93)90177-B","volume":"48","author":"H. Karloff","year":"1993","unstructured":"Karloff, H.: Fast algorithms for approximately counting mismatches. Information Processing Letters\u00a048(2), 53\u201360 (1993)","journal-title":"Information Processing Letters"},{"key":"8_CR15","unstructured":"Kosaraju, S.R.: Efficient string matching (1987) (manuscript)"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching in the presence of errors. In: FOCS 1985: Proc. 26th Annual Symp. Foundations of Computer Science, pp. 126\u2013136 (1985)","DOI":"10.1109\/SFCS.1985.22"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"G.M. Landau","year":"1986","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching with k mismatches. Theoretical Computer Science\u00a043, 239\u2013249 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"8_CR19","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0000(88)90045-1","volume":"37","author":"G.M. Landau","year":"1988","unstructured":"Landau, G.M., Vishkin, U.: Fast string matching with k differences. Journal of Computer System Sciences\u00a037(1), 63\u201378 (1988)","journal-title":"Journal of Computer System Sciences"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Porat, B., Porat, E.: Exact and approximate pattern matching in the streaming model. In: FOCS 2009: Proc. 50th Annual Symp. Foundations of Computer Science, pp. 315\u2013323 (2009)","DOI":"10.1109\/FOCS.2009.11"},{"key":"8_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-540-70575-8_8","volume-title":"Automata, Languages and Programming","author":"M. Ru\u017ei\u0107","year":"2008","unstructured":"Ru\u017ei\u0107, M.: Constructing Efficient Dictionaries in Close to Sorting Time. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 84\u201395. Springer, Heidelberg (2008)"},{"key":"8_CR22","unstructured":"Simon, I.: String matching algorithms and automata. In: First American Workshop on String Processing, pp. 151\u2013157 (1993)"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Some complexity questions related to distributive computing. In: STOC 1979: Proc. 11th Annual ACM Symp. Theory of Computing, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31265-6_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T22:43:00Z","timestamp":1743374580000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31265-6_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642312649","9783642312656"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31265-6_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}