stringsearch

Stringsearch refers to the process of locating occurrences of a substring or pattern within a larger text or sequence. It is a fundamental operation in text processing, data mining, bioinformatics, and software development. The simplest approach is a naive scan, checking each starting position for a match, which in the worst case takes O(nm) time for a text of length n and a pattern of length m.

More advanced algorithms improve efficiency by avoiding unnecessary comparisons. Knuth-Morris-Pratt (KMP) builds a failure function that allows the scan to skip ahead when a mismatch occurs, giving O(n + m) time with linear preprocessing of the pattern. Boyer-Moore uses heuristics to examine characters from right to left, often performing much faster in practice and with worst-case O(nm) guarantees. Rabin-Karp uses a rolling hash to compare pattern and text substrings, achieving O(n + m) expected time and easy support for multiple patterns through hashing.

For multiple patterns, Aho-Corasick builds a finite automaton from all patterns, enabling simultaneous search in O(n + total matches). Suffix structures, such as suffix trees and suffix arrays, provide powerful tools for exact and approximate substring queries on large texts.

Approximate or fuzzy string searching handles near matches and edit distances, useful in spell-checking and bioinformatics. Implementations appear in standard libraries and tools, including substring search functions in programming languages and search utilities.