Exact String Matching Algorithm

An Exact String Matching Algorithm is a string matching algorithm that can be implemented by an Exact String Matching System (to solve an exact string matching task).

• Context:
  • It can range from being a Single-Pattern Exact String Matching Algorithm, to being a Finite-Pattern Set Exact String Matching Algorithm, to being an Infinite-Pattern Set Exact String Matching Algorithm.
  • …
• Example(s):
  • Naïve String Matching Algorithm 0 (no preprocessing) Θ((n-m+1) m)
  • Finite State Automaton String Matching Algorithm Θ(m |Σ|) Θ(n)
  • Knuth-Morris-Pratt String Matching Algorithm Θ(m) Θ(n)
  • Boyer-Moore String Matching Algorithm Θ(m + |Σ|) Ω(n/m), O(n)
  • Bitap String Matching Algorithm (shift-or, shift-and, Baeza-Yates-Gonnet) Θ(m + |Σ|) O(mn)
  • a Finite-Pattern Set Exact String Matching Algorithm, such as:
    • an Aho-Corasick String Matching Algorithm, worst time: O(n+m), space: O(m).
    • a Rabin-Karp String Matching Algorithm Θ(m) average Θ(n+m), worst Θ((n-m+1) m)
• See: Approximate String Matching Algorithm.

---

---

References

2012

• (Wikipedia, 2012) ⇒ http://en.wikipedia.org/wiki/String_searching_algorithm
  • QUOTE: The various algorithms can be classified by the number of patterns each uses.

     Single pattern algorithms

     Algorithms using finite set of patterns

     Algorithms using infinite number of patterns

---