{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T06:58:02Z","timestamp":1758265082423},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642102165"},{"type":"electronic","value":"9783642102172"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10217-2_26","type":"book-chapter","created":{"date-parts":[[2009,11,9]],"date-time":"2009-11-09T15:52:03Z","timestamp":1257781923000},"page":"254-265","source":"Crossref","is-referenced-by-count":2,"title":["Fast Convolutions and Their Applications in Approximate String Matching"],"prefix":"10.1007","author":[{"given":"Kimmo","family":"Fredriksson","sequence":"first","affiliation":[]},{"given":"Szymon","family":"Grabowski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. In: Proceedings of the 11th ACM-SIAM Annual Symposium on Discrete Algorithms, San Francisco, CA, pp. 794\u2013803 (2000)"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. System Sci.\u00a047, 424\u2013436 (1993)","journal-title":"J. Comput. System Sci."},{"key":"26_CR3","unstructured":"Fischer, M.J., Paterson, M.: String matching and other products. In: Karp, R.M. (ed.) Proceedings of the SIAM-AMS Complexity of Computation, Providence, RI, pp. 113\u2013125 (1974)"},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/11496656_7","volume-title":"Combinatorial Pattern Matching","author":"P. Clifford","year":"2005","unstructured":"Clifford, P., Clifford, R., Iliopoulos, C.S.: Faster algorithms for \u03b4,\u03b3-matching and related problems. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol.\u00a03537, pp. 68\u201378. Springer, Heidelberg (2005)"},{"key":"26_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/11496656_9","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2005","unstructured":"Amir, A., Lipsky, O., Porat, E., Umanski, J.: Approximate matching in the L\n                  1 metric. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol.\u00a03537, pp. 91\u2013103. Springer, Heidelberg (2005)"},{"key":"26_CR6","first-page":"166","volume-title":"Proceedings of the 39th IEEE Annual Symposium on Foundations of Computer Science","author":"P. Indyk","year":"1998","unstructured":"Indyk, P.: Faster algorithms for string matching problems: matching the convolution bound. In: Proceedings of the 39th IEEE Annual Symposium on Foundations of Computer Science, pp. 166\u2013173. IEEE Computer Society Press, Los Alamitos (1998)"},{"issue":"6","key":"26_CR7","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":"26_CR8","unstructured":"Kosaraju, S.R.: Efficient string matching (1987) (manuscript)"},{"issue":"2-3","key":"26_CR9","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. Theor. Comput. Sci.\u00a043(2-3), 239\u2013249 (1986)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"26_CR10","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/j.ipl.2007.08.021","volume":"105","author":"S. Grabowski","year":"2008","unstructured":"Grabowski, S., Fredriksson, K.: Bit-parallel string matching under Hamming distance in O(n\u2308m\/w \u2309) worst case time. Information Processing Letters\u00a0105(5), 182\u2013187 (2008)","journal-title":"Information Processing Letters"},{"issue":"3","key":"26_CR11","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.jcss.2008.08.005","volume":"75","author":"C. Linhart","year":"2009","unstructured":"Linhart, C., Shamir, R.: Faster pattern matching with character classes using prime number encoding. Journal of Computer and System Sciences\u00a075(3), 155\u2013162 (2009)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"26_CR12","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/8307.8309","volume":"17","author":"Z. Galil","year":"1986","unstructured":"Galil, Z., Giancarlo, R.: Improved string matching with k mismatches. SIGACT News\u00a017(4), 52\u201354 (1986)","journal-title":"SIGACT News"},{"issue":"1","key":"26_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0885-064X(88)90008-8","volume":"4","author":"Z. Galil","year":"1988","unstructured":"Galil, Z., Giancarlo, R.: Data structures and algorithms for approximate string matching. J. Complexity\u00a04(1), 33\u201372 (1988)","journal-title":"J. Complexity"},{"issue":"4","key":"26_CR14","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/959122.959123","volume":"31","author":"M. Thorup","year":"2003","unstructured":"Thorup, M.: Combinatorial power in multimedia processors. SIGARCH Comput. Archit. News\u00a031(4), 5\u201311 (2003)","journal-title":"SIGARCH Comput. Archit. News"},{"key":"26_CR15","unstructured":"Thorup, M.: On AC0 implementations of fusion trees and atomic heaps. In: Proceedings of the 14th ACM-SIAM Annual Symposium on Discrete Algorithms, Philadelphia, PA, USA, pp. 699\u2013707. Society for Industrial and Applied Mathematics (2003)"},{"key":"26_CR16","unstructured":"Knuth, D.: The art of computer programming: Combinatorial algorithms. Pre-fascicle 1a. Draft of section 7.1.3: Bitwise tricks and techniques (2008), \n                    \n                      http:\/\/www-cs-faculty.stanford.edu\/~knuth\/fasc1a.ps.gz"},{"key":"26_CR17","unstructured":"Smith III, J.O.: Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications, 2nd edn. W3K Publishing (2007)"},{"key":"26_CR18","volume-title":"Ramsey theory","author":"R.L. Graham","year":"1990","unstructured":"Graham, R.L., Rothschild, B.L.: Ramsey theory, 2nd edn. Wiley-Interscience, New York (1990)","edition":"2"},{"key":"26_CR19","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1112\/jlms\/s1-28.1.104","volume":"28","author":"K.F. Roth","year":"1953","unstructured":"Roth, K.F.: On certain sets of integers. J. London Math. Soc.\u00a028, 104\u2013109 (1953)","journal-title":"J. London Math. Soc."},{"issue":"1","key":"26_CR20","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s11854-008-0020-x","volume":"104","author":"J. Bourgain","year":"2008","unstructured":"Bourgain, J.: Roth\u2019s theorem on progressions revisited. Journal d\u2019Analyse Math\u00e9matique\u00a0104(1), 155\u2013192 (2008)","journal-title":"Journal d\u2019Analyse Math\u00e9matique"},{"key":"26_CR21","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1073\/pnas.32.12.331","volume":"23","author":"F.A. Behrend","year":"1946","unstructured":"Behrend, F.A.: On sets of integers which contain no three in arithmetic progression. Proc. Nat. Acad. Sci.\u00a023, 331\u2013332 (1946)","journal-title":"Proc. Nat. Acad. Sci."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10217-2_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T11:34:30Z","timestamp":1619782470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10217-2_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642102165","9783642102172"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10217-2_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}