Efficient algorithms for multiple pattern matching

Front Cover
University of Wisconsin--Madison, 1986 - Pattern perception - 184 pages

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.


A simple algorithm
A second timespace tradeoff

3 other sections not shown

Common terms and phrases

abort abort matches against the text Aho and Corasick Aho-Corasick algorithm Aho-Corasick machine algorithm consults algorithm remembers ancestor Bangalore begin in R(m bit vectors Boyer-Moore algorithm chapter char(C charging argument Commentz-Walter's algorithm compute Computer Sciences computing the shift configuration construct critical node critical path critical with respect current node current trie currently remembered d(wi defined definition of critical denote depth depth-first depth-first search depth-first traversal descendant w distinct displacement values Doctor of Philosophy don't-cares end at text end in L(m extend the Boyer-Moore failure function fc-mesh Figure fingerprints finite state machine Galil given given match given open match Guibas heuristic However Input Iog4 D Knuth Knuth-Morris-Pratt algorithm labeled leaf lemma length N linear log D m-heavy matches m-light machine matches begin matches mi matches remembered matches that begin matching phase matching the pattern memory function mismatch multi-dimensional arrays multiple patterns node w nonlinear nonperiodic matches occurs Odlyzko open match overlap pattern matching periodic matches Peter Spear potentially critical precompute pref w prefix preprocess the trie preprocessing phase previous matches problem Proof proper prefix region of text regular expression remembered matches right end root satisfies set of patterns Sfc(m shift function shortest pattern simple algorithm space bounds sublinear subsequent match substring suffix terminating character text characters text of length text position text region text string Therefore time-space tradeoff trie against trie node University of Wisconsin UNIX wmin word(v

Bibliographic information