substringsearch

Substring search is the problem of finding occurrences of a pattern string within a larger text. It is a core operation in text processing, search tools, compilers, and bioinformatics. The simplest method is the naive algorithm, which aligns the pattern at each position of the text and compares characters. This runs in O(nm) time in the worst case and uses constant extra space.

Efficient algorithms reduce the number of character comparisons. The Knuth–Morris–Pratt (KMP) algorithm uses a preprocessed table of longest proper prefix-suffix values to skip unnecessary comparisons, achieving O(n + m) time. The Z-algorithm also runs in O(n + m) by constructing a Z-array that encodes match lengths. The Rabin–Karp method uses a rolling hash to compare substrings, with expected O(n + m) time and O(m) space; worst-case O(nm) if many hash collisions occur.

Boyer–Moore is a highly effective approach for single-pattern search, employing bad-character and good-suffix heuristics to skip large text portions, often yielding sublinear average-case time on typical alphabets. For multiple patterns, Aho–Corasick builds a finite automaton to search all patterns simultaneously in O(n + total pattern length + number of matches).

Variants and considerations include case sensitivity, overlapping occurrences, streaming or online searching, and Unicode handling. Implementations must weigh preprocessing cost, memory usage, and hash collision risk. Applications span text editors, grep-like utilities, database search, data mining, and biological sequence analysis. Substring search remains a foundational topic in exact, approximate, and dynamic pattern matching for large-scale data.