Pattern Matching Algorithms
Alberto Apostolico, Zvi Galil
Oxford University Press, May 29, 1997 - Computers - 400 pages
Issues of matching and searching on elementary discrete structures arise pervasively in computer science and many of its applications, and their relevance is expected to grow as information is amassed and shared at an accelerating pace. Several algorithms were discovered as a result of these needs, which in turn created the subfield of Pattern Matching. This book provides an overview of the current state of Pattern Matching as seen by specialists who have devoted years of study to the field. It covers most of the basic principles and presents material advanced enough to faithfully portray the current frontier of research. Because of these recent advances, this is the right time for a book that brings together information relevant to both graduate students and specialists in need of an in-depth reference.
What people are saying - Write a review
We haven't found any reviews in the usual places.
2 Offline Parallel Exact String Searching
3 Online String Searching
4 Serial Computations of Levenshtein Distances
5 Parallel Computations of Levenshtein Distances
6 Approximate String Searching
Other editions - View all
alignment alphabet approximation array assigned assume automaton block candidates compacted trie complexity compression concave consider constant construction contains convex CRCW-PRAM defined definition deletions denote diagonal dynamic programming edit distance efficient equivalence class EREW-PRAM function Galil given Greedy implementation input integer interval k-block labeled left list Lemma length Levenshtein distance linear longest common lower bound macro strings matching algorithm matrix minima mismatch MP algorithm node O(log log O(n log obtained occurrence optimal pair parallel algorithm partition path pattern matching period position prefix problem procedure processors Proof recurrence resp root scan search phase Section sequence sequence alignment shift shortest common superstring shortest superstring space stage step string editing problem string matching string searching algorithm submatrices subproblem subset substring subtree subword suffix automaton suffix tree symbol comparisons Theorem totally monotone Tree(f Vishkin witness