Definition: The problem of finding occurrence(s) of a pattern string within another string or body of text. There are many different algorithms for efficient searching.
Also known as exact string matching, string searching, text searching.
Generalization (I am a kind of ...)
Specialization (... is a kind of me.)
brute force string search, Knuth-Morris-Pratt algorithm, Boyer-Moore, Zhu-Takaoka, quick search, deterministic finite automata string search, Karp-Rabin, Shift-Or, Aho-Corasick, Smith algorithm, strsrch.
See also string matching with errors, optimal mismatch, phonetic coding, string matching on ordered alphabets, suffix tree, inverted index.
Note: For large collections that are searched often, it may be far faster, though more complicated, to start with an inverted index. The name "exact string matching" is in contrast to string matching with errors.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 20 July 2018.
HTML page formatted Tue Feb 12 10:57:43 2019.
Cite this as:
Paul E. Black, "string matching", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 20 July 2018. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/stringMatching.html