Exact String Matching Task

An Exact String Matching Task is a string matching task that is required to find a place where one or more string patterns are found within a data string.

• Context:
  • Inputs: a String; and a String Pattern Set.
  • It an range from being a Single-Pattern Exact String Matching Task, to being a Finite-Pattern Set Exact String Matching Task, to being an Infinite-Pattern Set Exact String Matching Task.
  • It can be solved by an Exact String Matching System (that implements an exact string matching algorithm).
  • …
• Example(s):
  • Finding a specific phrase in a book.
  • Locating specific DNA sequences within a larger genome sequence.
  • …
• Counter-Example(s):
  • Approximate String Matching, allows for mismatches or errors in the pattern.
• See: String Searching Algorithm, Pattern Matching, Regular Expression.

---

---

References

2012

• (Wikipedia, 2012) ⇒ http://en.wikipedia.org/wiki/String_searching_algorithm
  • QUOTE: In computer science, string searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text.

    Let Σ be an alphabet (finite set). Formally, both the pattern and searched text are vectors of elements of Σ. The Σ may be a usual human alphabet (for example, the letters A through Z in the Latin alphabet). Other applications may use binary alphabet (Σ = {0,1}) or DNA alphabet (Σ = {A,C,G,T}) in bioinformatics.

    In practice, how the string is encoded can affect the feasible string search algorithms. In particular if a variable width encoding is in use then it is slow (time proportional to N) to find the Nth character. This will significantly slow down many of the more advanced search algorithms. A possible solution is to search for the sequence of code units instead, but doing so may produce false matches unless the encoding is specifically designed to avoid it.

---