{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T16:28:09Z","timestamp":1746462489881},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,1]]},"DOI":"10.1007\/bf01942606","type":"journal-article","created":{"date-parts":[[2005,7,26]],"date-time":"2005-07-26T20:24:55Z","timestamp":1122409495000},"page":"50-67","source":"Crossref","is-referenced-by-count":43,"title":["A subquadratic algorithm for approximate limited expression matching"],"prefix":"10.1007","volume":"15","author":[{"given":"Sun","family":"Wu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"U.","family":"Manber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Myers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01942606_CR1","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K. Abrahamson","year":"1987","unstructured":"K. Abrahamson, Generalized string matching,SIAM J. Comput.,16 (1987), 1039\u20131051.","journal-title":"SIAM J. Comput."},{"key":"BF01942606_CR2","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A. V. Aho","year":"1975","unstructured":"A. V. Aho and M. J. Corasick, Efficient string matching: an aid to bibliographic search,Comm. ACM,18 (1975), 333\u2013340.","journal-title":"Comm. ACM"},{"key":"BF01942606_CR3","first-page":"487","volume":"194","author":"V. L. Arlazarov","year":"1970","unstructured":"V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev, On economic construction of the transitive closure of a directed graph,Dokl. Akad. Nauk SSSR,194 (1970), 487\u2013488 (in Russian). English translation inSoviet Math. Dokl.,11 (1975), 1209\u20131210.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"BF01942606_CR4","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/135239.135243","volume":"35","author":"R. A. Baeza-Yates","year":"1992","unstructured":"R. A. Baeza-Yates and G. H. Gonnet, A new approach to text searching,Comm. ACM,35 (1992), 74\u201382.","journal-title":"Comm. ACM"},{"key":"BF01942606_CR5","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. ACM,20 (1977), 762\u2013772.","journal-title":"Comm. ACM"},{"key":"BF01942606_CR6","doi-asserted-by":"crossref","unstructured":"W. I. Chang and E. L. Lawler, Approximate string matching in sublinear expected time,Proc. 31st Symp. on Foundations of Computer Science, 1990, pp. 116\u2013124.","DOI":"10.1109\/FSCS.1990.89530"},{"key":"BF01942606_CR7","doi-asserted-by":"crossref","unstructured":"W. I. Chang and J. Lampe, Theoretical and empirical comparisons of approximate string matching algorithms,Proc. 3rd Symp. on Combinatorial Pattern Matching, Tucson, AZ, April 1992, pp. 172\u2013181.","DOI":"10.1007\/3-540-56024-6_14"},{"key":"BF01942606_CR8","doi-asserted-by":"crossref","unstructured":"B. Commentz-Walter, A string matching algorithm fast on the average,Proc. 6th Internal. Colloq. on Automata, Languages, and Programming, 1979, pp. 118\u2013132.","DOI":"10.1007\/3-540-09510-1_10"},{"key":"BF01942606_CR9","unstructured":"M. Fischev and M. Paterson, String matching and other products,Proc. 7th SIAM-AMS Symp. on Complexity of Computation, 1974, pp. 113\u2013125."},{"key":"BF01942606_CR10","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1137\/0219067","volume":"19","author":"Z. Galil","year":"1990","unstructured":"Z. Galil and K. Park, An improved algorithm for approximate string matching,SIAM J. Comput.,19 (1990), 989\u2013999.","journal-title":"SIAM J. Comput."},{"key":"BF01942606_CR11","doi-asserted-by":"crossref","first-page":"323","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 (1977), 323\u2013350.","journal-title":"SIAM J. Comput."},{"key":"BF01942606_CR12","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0022-0000(88)90045-1","volume":"37","author":"G. M. Landau","year":"1988","unstructured":"G. M. Landau and U. Vishkin, Fast string matching withk differences,J. Comput. System Sci.,37 (1988), 63\u201378.","journal-title":"J. Comput. System Sci."},{"key":"BF01942606_CR13","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W. J. Masek","year":"1980","unstructured":"W. J. Masek and M. S. Paterson, A faster algorithm for computing string edit distances,J. Comput. System Sci.,20 (1980), 18\u201331.","journal-title":"J. Comput. System Sci."},{"key":"BF01942606_CR14","unstructured":"E. W. Myers, Incremental Alignment Algorithms and their Applications, Technical Report 86-22, Department of Computer Science, University of Arizona, 1986."},{"key":"BF01942606_CR15","doi-asserted-by":"crossref","unstructured":"E. W. Myers, A Sublinear Algorithm for Approximate Keywords Searching, Technical Report TR-90-25, Department of Computer Science, University of Arizona, 1990. Also inAlgorithmica,12 (1994), 345\u2013374.","DOI":"10.1007\/BF01185432"},{"key":"BF01942606_CR16","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1145\/128749.128755","volume":"39","author":"E. W. Myers","year":"1992","unstructured":"E. W. Myers, A four-Russians algorithm for regular expression pattern matching,J. Assoc. Comput. Mach.,39 (1992), 430\u2013448.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01942606_CR17","series-title":"NATO ASI Series, Vol. F12","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-3-642-82456-2_2","volume-title":"Combinatorial Algorithms on Words","author":"R. Pinter","year":"1985","unstructured":"R. Pinter, Efficient string matching with don't-care patterns, inCombinatorial Algorithms on Words (A. Apostilico and Z. Galil, eds.), NATO ASI Series, Vol. F12, Springer-Verlag, New York, 1985, 11\u201329."},{"key":"BF01942606_CR18","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P. H. Sellers","year":"1980","unstructured":"P. H. Sellers, The theory and computations of evolutionary distances: pattern recognition,J. Algorithms,1 (1980), 359\u2013373.","journal-title":"J. Algorithms"},{"issue":"2","key":"BF01942606_CR19","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1137\/0222018","volume":"22","author":"J. Tarhio","year":"1993","unstructured":"J. Tarhio and E. Ukkonen, Approximate Boyer-Moore string matching,SIAM J. Comput.,22(2) (1993), 243\u2013260.","journal-title":"SIAM J. Comput."},{"key":"BF01942606_CR20","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","volume":"6","author":"E. Ukkonen","year":"1985","unstructured":"E. Ukkonen, Finding approximate patterns in strings,J. Algorithms,6 (1985), 132\u2013137.","journal-title":"J. Algorithms"},{"key":"BF01942606_CR21","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"E. Ukkonen","year":"1992","unstructured":"E. Ukkonen, Approximate string-matching withq-grams and maximal matches,Theoret. Comput. Sci.,92(1992), 191\u2013211.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01942606_CR22","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF01769703","volume":"10","author":"E. Ukkonen","year":"1993","unstructured":"E. Ukkonen and D. Wood, Approximate string matching with suffix automata,Algorithmica,10 (1993), 353\u2013364.","journal-title":"Algorithmica"},{"key":"BF01942606_CR23","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. A. Wagner","year":"1974","unstructured":"R. A. Wagner and M. J. Fisher, The string to string correction problem,J. Assoc. Comput. Mach.,21 (1974), 168\u2013173.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01942606_CR24","unstructured":"S. Wu and U. Manber, Agrep-a fast approximate pattern-matching tool,Proc. Usenix Winter 1992Technical Conference, San Francisco, January 1992, pp. 153\u2013162."},{"key":"BF01942606_CR25","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/135239.135244","volume":"35","author":"S. Wu","year":"1992","unstructured":"S. Wu and U. Manber, Fast text searching allowing errors,Comm. ACM,35 (1992), 83\u201391.","journal-title":"Comm. ACM"},{"key":"BF01942606_CR26","unstructured":"S. Wu, U. Manber, and E. W. Myers, A sub-quadratic algorithm for approximate regular expression matching,J. of Algorithms, to appear."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01942606.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01942606\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01942606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T10:46:46Z","timestamp":1586342806000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01942606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,1]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["BF01942606"],"URL":"https:\/\/doi.org\/10.1007\/bf01942606","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,1]]}}}