Hubbry Logo
String-searching algorithmString-searching algorithmMain
Open search
String-searching algorithm
Community hub
String-searching algorithm
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
String-searching algorithm
String-searching algorithm
String-searching algorithm
View on Wikipedia
from Wikipedia

A string-searching algorithm, sometimes called string-matching algorithm, is an algorithm that searches a body of text for portions that match by pattern.

A basic example of string searching is when the pattern and the searched text are arrays of elements of an alphabet (finite set) Σ. Σ may be a human language alphabet, for example, the letters A through Z and other applications may use a binary alphabet (Σ = {0,1}) or a DNA alphabet (Σ = {A,C,G,T}) in bioinformatics.

In practice, the method of feasible string-search algorithm may be affected by the string encoding. In particular, if a variable-width encoding is in use, then it may be slower to find the Nth character, perhaps requiring time proportional to N. This may significantly slow some search algorithms. One of many possible solutions 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.[citation needed]

Overview

[edit]

The most basic case of string searching involves one (often very long) string, sometimes called the haystack, and one (often very short) string, sometimes called the needle. The goal is to find one or more occurrences of the needle within the haystack. For example, one might search for to within: 

Some books are to be tasted, others to be swallowed, and some few to be chewed and digested.

One might request the first occurrence of "to", which is the fourth word; or all occurrences, of which there are 3; or the last, which is the fifth word from the end.

Very commonly, however, various constraints are added. For example, one might want to match the "needle" only where it consists of one (or more) complete words—perhaps defined as not having other letters immediately adjacent on either side. In that case a search for "hew" or "low" should fail for the example sentence above, even though those literal strings do occur.

Another common example involves "normalization". For many purposes, a search for a phrase such as "to be" should succeed even in places where there is something else intervening between the "to" and the "be":

  • More than one space
  • Other "whitespace" characters such as tabs, non-breaking spaces, line-breaks, etc.
  • Less commonly, a hyphen or soft hyphen
  • In structured texts, tags or even arbitrarily large but "parenthetical" things such as footnotes, list-numbers or other markers, embedded images, and so on.

Many symbol systems include characters that are synonymous (at least for some purposes):

  • Latin-based alphabets distinguish lower-case from upper-case, but for many purposes string search is expected to ignore the distinction.
  • Many languages include ligatures, where one composite character is equivalent to two or more other characters.
  • Many writing systems involve diacritical marks such as accents or vowel points, which may vary in their usage, or be of varying importance in matching.
  • DNA sequences can involve non-coding segments which may be ignored for some purposes, or polymorphisms that lead to no change in the encoded proteins, which may not count as a true difference for some other purposes.
  • Some languages have rules where a different character or form of character must be used at the start, middle, or end of words.

Finally, for strings that represent natural language, aspects of the language itself become involved. For example, one might wish to find all occurrences of a "word" despite it having alternate spellings, prefixes or suffixes, etc.

Another more complex type of search is regular expression searching, where the user constructs a pattern of characters or other symbols, and any match to the pattern should fulfill the search. For example, to catch both the American English word "color" and the British equivalent "colour", instead of searching for two different literal strings, one might use a regular expression such as: 

colou?r

where the "?" conventionally makes the preceding character ("u") optional.

This article mainly discusses algorithms for the simpler kinds of string searching.

A similar problem introduced in the field of bioinformatics and genomics is the maximal exact matching (MEM).[1] Given two strings, MEMs are common substrings that cannot be extended left or right without causing a mismatch.[2]

Examples of search algorithms

[edit]
[edit]

A simple and inefficient way to see where one string occurs inside another is to check at each index, one by one. First, we see if there is a copy of the needle starting at the first character of the haystack; if not, we look to see if there's a copy of the needle starting at the second character of the haystack, and so forth. In the normal case, we only have to look at one or two characters for each wrong position to see that it is a wrong position, so in the average case, this takes O(n + m) steps, where n is the length of the haystack and m is the length of the needle; but in the worst case, searching for a string like "aaaab" in a string like "aaaaaaaaab", it takes O(nm)

[edit]

In this approach, backtracking is avoided by constructing a deterministic finite automaton (DFA) that recognizes a stored search string. These are expensive to construct—they are usually created using the powerset construction—but are very quick to use. For example, the DFA shown to the right recognizes the word "MOMMY". This approach is frequently generalized in practice to search for arbitrary regular expressions.

Stubs

[edit]

Knuth–Morris–Pratt computes a DFA that recognizes inputs with the string to search for as a suffix, Boyer–Moore starts searching from the end of the needle, so it can usually jump ahead a whole needle-length at each step. Baeza–Yates keeps track of whether the previous j characters were a prefix of the search string, and is therefore adaptable to fuzzy string searching. The bitap algorithm is an application of Baeza–Yates' approach.

Index methods

[edit]

Faster search algorithms preprocess the text. After building a substring index, for example a suffix tree or suffix array, the occurrences of a pattern can be found quickly. As an example, a suffix tree can be built in time, and all occurrences of a pattern can be found in time under the assumption that the alphabet has a constant size and all inner nodes in the suffix tree know what leaves are underneath them. The latter can be accomplished by running a DFS algorithm from the root of the suffix tree.

Other variants

[edit]

Some search methods, for instance trigram search, are intended to find a "closeness" score between the search string and the text rather than a "match/non-match". These are sometimes called "fuzzy" searches.

Classification of search algorithms

[edit]

Classification by a number of patterns

[edit]

The various algorithms can be classified by the number of patterns each uses.

Single-pattern algorithms

[edit]

In the following compilation, m is the length of the pattern, n the length of the searchable text, and k = |Σ| is the size of the alphabet.

Algorithm Preprocessing time Matching time[1] Space
Naïve algorithm none Θ(n+m) in average,
O(mn) 		none
Automaton-based matching Θ(km) Θ(n) Θ(km)
Rabin–Karp Θ(m) Θ(n) in average,
O(mn) at worst 		O(1)
Knuth–Morris–Pratt Θ(m) Θ(n) Θ(m)
Boyer–Moore Θ(m + k) O(n/m) at best,
O(mn) at worst 		Θ(k)
Two-way algorithm[3][2] Θ(m) O(n) O(log(m))
Backward Non-Deterministic DAWG Matching (BNDM)[4][3] O(m) Ω(n/m) at best,
O(mn) at worst
Backward Oracle Matching (BOM)[5] O(m) O(mn)
1.^ Asymptotic times are expressed using O, Ω, and Θ notation.
2.^ Used to implement the memmem and strstr search functions in the glibc[6] and musl[7] C standard libraries.
3.^ Can be extended to handle approximate string matching and (potentially-infinite) sets of patterns represented as regular languages.[citation needed]

The Boyer–Moore string-search algorithm has been the standard benchmark for the practical string-search literature.[8]

Algorithms using a finite set of patterns

[edit]

In the following compilation, M is the length of the longest pattern, m their total length, n the length of the searchable text, o the number of occurrences.

Algorithm Extension of Preprocessing time Matching time[4] Space
Aho–Corasick Knuth–Morris–Pratt Θ(m) Θ(n + o) Θ(m)
Commentz-Walter Boyer-Moore Θ(m) Θ(M * n) worst case
sublinear in average[9] 		Θ(m)
Set-BOM Backward Oracle Matching

Algorithms using an infinite number of patterns

[edit]

Naturally, the patterns can not be enumerated finitely in this case. They are represented usually by a regular grammar or regular expression.

Classification by the use of preprocessing programs

[edit]

Other classification approaches are possible. One of the most common uses preprocessing as main criteria.

Classes of string searching algorithms[10]
Text not preprocessed Text preprocessed
Patterns not preprocessed Elementary algorithms Index methods
Patterns preprocessed Constructed search engines Signature methods[11]

Classification by matching strategies

[edit]

Another one classifies the algorithms by their matching strategy:[12]

  • Match the prefix first (Knuth–Morris–Pratt, Shift-And, Aho–Corasick)
  • Match the suffix first (Boyer–Moore and variants, Commentz-Walter)
  • Match the best factor first (BNDM, BOM, Set-BOM)
  • Other strategy (Naïve, Rabin–Karp, Vectorized)

Real-time string matching

[edit]

In real-time string matching, one requires the matcher to output a response after reading each character of the text, that indicates whether this is the last character of a match. The response has to be given within constant time. The requirement regarding preprocessing vary: O(m) preprocessing may be allowed after the pattern is read (but before the reading of the text), or a stricter requirement may be posed according to which the matcher has to also pause for at most a constant time after reading any character of the pattern (including the last). For the more lenient version, if one does not mind that the preprocessing time and memory requirement dependend on the size of the alphabet, a real-time solution is provided by automaton matching. Zvi Galil developed a method to turn certain algorithms into real-time algorithms, and applied it to produce a variant of the KMP matcher that runs in real time under the strict requirement.[13]

String searching with don't cares

[edit]

In this version of the string searching problem, there is a special symbol, ø (read: don't care), which can match any other symbol (including another ø). Don't care symbols can appear either in the pattern or in the text. In 2002, an algorithm for this problem that runs in time has been given by Richard Cole and Ramesh Hariharan, improving on a solution from 1973 by Fischer and Paterson that has complexity , where k is the size of the alphabet.[14] Another algorithm, claimed simpler, has been proposed by Clifford and Clifford.[15]

See also

[edit]

References

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

String-searching algorithm

View on Grokipedia
from Grokipedia
A string-searching algorithm, also known as a string-matching algorithm, is a computational procedure for locating all occurrences of a specified pattern string of length m within a larger text string of length n. These algorithms form a of , enabling efficient in strings over finite alphabets. The problem arises frequently in practical settings, such as searching for words in documents using text editors or web browsers, identifying motifs in DNA sequences for bioinformatics, performing plagiarism detection, and powering search functionalities in compilers and information retrieval systems. Naive implementations, like the brute-force method, examine every possible alignment of the pattern against the text by comparing characters sequentially, resulting in a worst-case time complexity of O(nm), which becomes inefficient for large strings. To address this, optimized algorithms preprocess either the pattern or the text to avoid redundant comparisons, often achieving linear-time performance O(n + m) in the worst case. Key historical developments include the **, published in 1977, which constructs a failure function (or prefix table) during O(m) preprocessing to determine how much to shift the pattern upon a mismatch, allowing the search phase to proceed without in the text. Concurrently, the **, also introduced in 1977, matches the pattern from right to left and leverages two heuristics—the bad-character rule (skipping based on unseen characters) and the good-suffix rule (skipping based on partial matches)—to enable frequent large jumps, yielding sublinear average-case performance, especially for patterns longer than a few characters. Additional influential techniques encompass the , which uses functions for probabilistic matching with expected O(n + m) time but potential O(nm) worst-case due to hash collisions, and automaton-based approaches like the ** for simultaneous searches of multiple patterns. Advanced data structures, such as suffix trees (constructed in O(n) time) and suffix arrays, further enhance efficiency for repeated queries on the same text by preprocessing it into compact representations that support O(m + k) searches, where k is the number of occurrences. These methods balance preprocessing costs, space usage, and query speed, with choices depending on factors like alphabet size, pattern length, and whether exact or approximate matching is required.

Introduction

Definition and Problem Statement

A string-searching algorithm, also known as exact string matching, is a method to locate all occurrences of a given pattern string PP within a larger text string TT. Both strings are sequences of characters drawn from a finite Σ\Sigma, with TT having length n=∣T∣n = |T| and PP having length m=∣P∣m = |P|, where typically m≤nm \leq n. The core problem is formally defined as follows: given the input pair (T,P)(T, P), identify and report all starting positions ii (where 0≤i≤n−m0 \leq i \leq n - m) such that the T[i…i+m−1]T[i \dots i+m-1] exactly equals PP. The output is a list of these matching indices ii, representing the positions where PP appears in TT. This formulation assumes exact matching, meaning no errors or approximations are allowed in the comparison. Standard string matching reports all occurrences, which may overlap—for instance, in the text "aaa" searching for "aa" yields matches at positions 0 and 1. Variants of the problem include determining only the existence of any match (without listing positions) or reporting a maximal set of non-overlapping occurrences, where no two matches share characters. These distinctions arise in applications such as text processing, where the choice depends on whether complete coverage or disjoint segments are required.

Historical Development and Importance

The development of string-searching algorithms began in the early days of , with early naive methods performing brute-force comparisons, resulting in quadratic in the worst case. These approaches, while simple, were insufficient for growing text-processing needs in early systems. A significant breakthrough came in 1977 with the Knuth-Morris-Pratt (KMP) algorithm, introduced by Donald E. Knuth, James H. Morris, and Vaughan R. Pratt, which achieved linear-time performance O(n + m) for text length n and pattern length m by preprocessing the pattern to avoid redundant comparisons. Key milestones followed closely. In 1975, Alfred V. Aho and Margaret J. Corasick developed an algorithm for multiple-pattern matching, building a to locate all occurrences of a set of keywords in linear time, enhancing efficiency for dictionary-based searches. The same year, 1977 saw Robert S. Boyer and J Strother Moore propose the Boyer-Moore algorithm, which skips portions of the text by comparing from the end of the pattern, often achieving sublinear average-case performance and proving highly practical for large texts. Concurrently, structures revolutionized the field; Peter Weiner introduced the concept in 1973 as a "position tree" for linear-time via compacted suffix representations. This was refined in the 1980s and culminated in Esko Ukkonen's 1995 online linear-time construction algorithm, making s more accessible for dynamic applications. String-searching algorithms hold central importance in computing, underpinning tools like compilers for and , text editors for find-and-replace operations, and for query processing and indexing. In bioinformatics, they enable efficient , crucial for genome assembly and motif discovery in large biological datasets. systems rely on them for in search engines, while security applications, such as intrusion detection systems like Snort, use multi-pattern variants to scan network traffic for malicious signatures in real time. These advancements profoundly impacted , shifting the paradigm from quadratic O(nm) naive methods to linear and sublinear bounds, which influenced broader algorithm design by emphasizing preprocessing and skipping techniques to exploit string redundancies. This evolution not only improved practical performance but also inspired research in related areas like compressed indexing and approximate matching.

Core Concepts

Text and Pattern Representation

In computer science, strings used in searching algorithms are typically represented as sequences of characters stored in contiguous memory locations, such as character arrays. In languages like C, strings are implemented as null-terminated arrays of characters, where a special null byte (ASCII 0) marks the end of the string, allowing functions to determine length without explicit storage. This approach facilitates efficient traversal but requires careful management to avoid buffer overflows. In contrast, higher-level languages like Java and Python treat strings as immutable objects, preventing in-place modifications to ensure thread safety and enable string sharing across the program. In Java, strings are stored as arrays of 16-bit UTF-16 code units, supporting Unicode characters where supplementary characters are represented by surrogate pairs. Similarly, Python represents strings as sequences of Unicode code points, with immutability enforced to promote functional programming practices and optimize memory usage through interning. Handling Unicode and multibyte characters adds complexity to string representation, as encodings like use variable-length byte sequences (1 to 4 bytes per character) to represent the full range of code points. This allows efficient storage for ASCII-dominant text while accommodating international scripts, but searching algorithms must account for code unit boundaries to avoid partial character matches. The encoding model structures this through layers including character encoding forms (e.g., , UTF-16) that map code points to code units, ensuring consistent processing across systems. For multibyte scenarios, such as in Chinese text processing, algorithms treat mixed single- and multi-byte characters by normalizing boundaries during representation. Preprocessing of text and pattern begins with computing their lengths, denoted as nn for the text and mm for the pattern, which establishes the scope for subsequent comparisons. Optional transformations, such as converting both to lowercase, enable case-insensitive matching by standardizing character representations without altering the underlying structure. This step is particularly useful in natural language applications where case variations should not affect results. Beyond basic arrays, data structures for text storage include linked lists, which offer advantages in dynamic environments by allowing efficient insertions and deletions at arbitrary positions without shifting elements, though they incur overhead from pointer storage and slower random access compared to arrays. Arrays, conversely, provide constant-time access via indexing, making them ideal for fixed-size texts in performance-critical searches, but resizing requires reallocation. For streaming inputs, where text arrives incrementally, buffers—such as circular queues or fixed-size arrays—temporarily hold data chunks to enable processing without loading the entire text into memory. In finite automata underlying some matching techniques, states are briefly represented using adjacency lists to model transitions over the alphabet, facilitating compact storage of sparse graphs. Memory considerations in preprocessing involve space trade-offs, where pattern-specific structures often require O(m)O(m) additional space to store auxiliary data like shift tables, balancing preprocessing time against search efficiency without excessive overhead for the text. This linear space usage for the pattern enables optimizations in algorithms while keeping overall proportional to input sizes.

Performance Metrics and Complexity Analysis

Performance in string-searching algorithms is primarily evaluated through time and space complexities, which quantify the computational resources required as functions of the input sizes: the text length nn and the pattern length mm, where typically n≫mn \gg m. Time complexity is divided into preprocessing (building auxiliary structures from the pattern) and searching (scanning the text for matches) phases. Preprocessing often requires O(m)O(m) time to analyze the pattern, while searching aims for efficiency across varying input distributions. In the worst case, searching can degrade to O(nm)O(nm) time, as seen in basic approaches where every possible alignment of the pattern against the text is exhaustively checked, leading to up to Θ(nm)\Theta(nm) character comparisons. For average-case analysis assuming random strings over an alphabet Σ\Sigma, searching time is often sublinear or linear, such as O(n+m)O(n + m) or better, due to early mismatches reducing unnecessary inspections. Space complexity measures the additional beyond the input text and . Auxiliary space is commonly O(m)O(m) for storing preprocessing tables or functions, resulting in total space O(n+m)O(n + m). Some methods achieve constant auxiliary space O(1)O(1), relying solely on the input, though this may limit preprocessing benefits. Practical implementations must balance this with memory hierarchies, where excessive auxiliary space can increase cache misses. Key performance metrics beyond asymptotic bounds include the number of character comparisons (both text and pattern characters inspected) and the total number of text character inspections, which directly impact runtime on real hardware. These are often lower in average cases for random inputs, where mismatches occur after few comparisons, but adversarial inputs can force maximum inspections. Empirical benchmarks on test suites, such as the Canterbury Corpus or DNA sequences, reveal practical speeds, with algorithms favoring fewer inspections outperforming others by factors of 2-10 on large texts. Practical factors significantly influence efficiency. The alphabet size ∣Σ∣|\Sigma| affects skipping potential: larger alphabets enable more mismatches and shifts, reducing inspections, while small alphabets (e.g., binary or DNA) demand specialized handling to avoid quadratic degradation. Cache efficiency is crucial for large nn, as algorithms with sequential text access and localized pattern checks minimize cache misses, improving throughput by up to 20-50% on modern processors compared to jump-heavy methods. Analysis models distinguish theoretical guarantees from real-world . Worst-case uses adversarial inputs to bound maximum use, ensuring reliability in hostile scenarios. Average-case models assume uniform random strings, yielding probabilistic bounds like expected O(n)O(n) inspections. Empirical evaluation via benchmarks on diverse datasets (e.g., English text, genomes) provides context-specific insights, often prioritizing metrics like inspections over pure time due to hardware variability.

Single-Pattern Algorithms

Single-pattern string-searching algorithms are designed to locate all occurrences of a single pattern string PP of length mm within a text string TT of length nn (where n≥mn \geq m). These algorithms focus on exact matching for one fixed pattern and employ a variety of strategies—including direct comparison, pattern preprocessing to compute auxiliary tables, heuristic skipping rules, and hashing—to optimize performance beyond the basic brute-force method. They offer different trade-offs: some prioritize simplicity with no preprocessing but risk quadratic time in the worst case, while others achieve linear or sublinear average-case performance through preprocessing or clever mismatch handling. The following subsections describe four classic examples: the naive string matching algorithm, the Knuth-Morris-Pratt (KMP) algorithm, the Boyer-Moore algorithm, and the Rabin-Karp algorithm.

Naive String Matching

The naive string matching algorithm, also known as the brute-force approach, searches for occurrences of a pattern string PP of length mm within a text string TT of length nn (where n≥mn \geq m) by systematically checking each possible alignment of PP against substrings of TT. For each starting position ii ranging from 0 to n−mn - m, the algorithm compares characters of PP with the corresponding characters in T[i…i+m−1]T[i \dots i + m - 1] sequentially from left to right, halting the comparison at the first mismatch and advancing to the next position i+1i + 1 only after a full match or complete mismatch check. This process reports all starting indices ii where a full match is found. The algorithm's implementation uses two nested loops: an outer loop over possible starting positions ii, and an inner loop over pattern positions jj from 0 to m−1m - 1. If all characters match for a given ii, the position is recorded as an occurrence.

function NaiveMatch(T, P): n = length(T) m = length(P) for i = 0 to n - m: j = 0 while j < m and T[i + j] == P[j]: j = j + 1 if j == m: report i as a match

function NaiveMatch(T, P): n = length(T) m = length(P) for i = 0 to n - m: j = 0 while j < m and T[i + j] == P[j]: j = j + 1 if j == m: report i as a match

This pseudocode captures the direct character-by-character verification without any preprocessing or optimization. In the worst case, the time complexity is O(nm)O(nm), occurring when many partial matches lead to extensive comparisons, such as searching for P="aaaaaab"P = \text{"aaaaaab"} (six 'a's followed by 'b') in T="aaaaaaaaaaaaab"T = \text{"aaaaaaaaaaaaab"} (thirteen 'a's followed by 'b'), where nearly every position requires checking almost all mm characters before a mismatch. Under the assumption of uniformly random characters from an alphabet of size c≥2c \geq 2, the average-case time complexity is O(n)O(n), as the expected number of comparisons per alignment is constant, leading to a linear total cost independent of mm. The space complexity is O(1)O(1) auxiliary space, beyond the input strings themselves, since no additional data structures are required. The primary advantages of naive string matching are its simplicity and lack of preprocessing overhead, making it straightforward to implement and suitable for small patterns or texts where quadratic time is acceptable. However, its disadvantages become pronounced for large mm relative to nn or in repetitive texts, where the worst-case quadratic time can lead to inefficiency compared to more advanced algorithms.

Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt (KMP) algorithm is a linear-time string-searching method for finding all occurrences of a pattern string PP of length mm within a text string TT of length nn, where n≥mn \geq m. Developed independently by , Vaughan Pratt, and James H. Morris, it improves upon naive string matching by leveraging internal structure in the pattern to skip unnecessary comparisons, ensuring that each position in the text is examined at most once. This approach is particularly effective for exact matching in single-pattern scenarios, as it preprocesses the pattern to build a failure function that guides efficient shifts during mismatches. The core of the KMP algorithm lies in its preprocessing step, which computes the failure function π\pi (also called the prefix table or partial match table) for the pattern PP. For each position jj in PP (where 0≤j<m0 \leq j < m), π\pi stores the length of the longest proper prefix of the substring P[0..j]P[0..j] that is also a suffix of P[0..j]P[0..j]. This function captures overlapping redundancies in the pattern, enabling the algorithm to "fail" gracefully without backtracking in the text. The failure function is initialized with \pi{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} = 0. For j=1j = 1 to m−1m-1, π\pi is determined by finding the largest k<j+1k < j+1 such that P[0..k−1]=P[j−k+1..j]P[0..k-1] = P[j-k+1..j]; if no such k>0k > 0 exists, then π=0\pi = 0. The computation itself runs in O(m)O(m) time by iteratively extending candidate matches and falling back using previously computed π\pi values to avoid quadratic comparisons. In the searching phase, a qq tracks the length of the current match starting from position ii in TT. The algorithm advances qq while characters match (T=PT = P), incrementing both ii and qq. On a mismatch, it sets q=π[q−1]q = \pi[q-1] to shift the pattern forward by q−π[q−1]q - \pi[q-1] positions, effectively using the overlap information to resume matching without re-examining prior text characters. A match is found whenever q=mq = m, at which point the occurrence starts at i−m+1i - m + 1, and qq is reset to π[q−1]\pi[q-1] to continue searching for overlaps. The overall time complexity of KMP is O(m)O(m) for preprocessing plus O(n)O(n) for searching, yielding a total of O(n+m)O(n + m), independent of the alphabet size. It requires O(m)O(m) additional space to store the π\pi array. This linear bound holds because the searching phase amortizes shifts such that the total number of operations is bounded by n+mn + m. To illustrate, consider the pattern P=P = "ababaca" (m=7m = 7). The failure function is computed as π=[0,0,1,2,3,0,1]\pi = [0, 0, 1, 2, 3, 0, 1]. For the substring up to index 4 ("ababa"), \pi{{grok:render&&&type=render_inline_citation&&&citation_id=4&&&citation_type=wikipedia}} = 3 because "aba" (length 3) is the longest prefix that matches the suffix. Similarly, after "ababac" at index 5, a mismatch leads to \pi{{grok:render&&&type=render_inline_citation&&&citation_id=5&&&citation_type=wikipedia}} = 0 since "c" shares no prefix-suffix overlap with earlier parts. This π\pi array allows the algorithm, during searching, to skip to a state of 3 after matching "ababa" and mismatching on the next character, recognizing the overlapping "aba".

Boyer-Moore Algorithm

The Boyer-Moore algorithm is a heuristic-based method for efficiently searching a single pattern string PP of length mm within a text string TT of length nn, where n≫mn \gg m. Developed by Robert S. Boyer and J Strother Moore, it compares characters from right to left, leveraging mismatches to skip large portions of the text, which makes it particularly effective for texts or patterns over large alphabets. Unlike left-to-right approaches, this rightward alignment allows the algorithm to exploit information from partial matches to compute maximal safe shifts, often achieving sublinear time performance in practice. Preprocessing in the Boyer-Moore algorithm constructs two tables to guide shifts during searching. The bad-character rule table, denoted bcbc for each character cc in the alphabet Σ\Sigma, stores the maximum shift distance when cc causes a mismatch; specifically, bcbc is mm if cc does not appear in PP, otherwise it is m−jm - j where jj is the rightmost position of cc in PP (0-based from the left). The good-suffix rule table gsgs for positions j=0j = 0 to m−1m-1 (where j=m−1j = m-1 indicates a full match) computes shifts based on the longest suffix of P[0..j]P[0..j] that matches a prefix of PP; more precisely, gsgs is the smallest shift that aligns the next occurrence of the matched suffix starting after position jj in PP, or mm if no such occurrence exists. These tables are built in O(m+∣Σ∣)O(m + |\Sigma|) time, enabling rapid lookups during the search phase. The searching phase aligns the right end of PP with position ii in TT (initially i=m−1i = m-1) and compares characters from right to left, starting at TT against P[m−1]P[m-1]. If all mm characters match, a occurrence is reported at i−m+1i - m + 1, and the search continues from i+1i + 1. On a mismatch at position jj (where PP aligns with T[i−(m−1−j)]T[i - (m-1 - j)]), the pattern shifts right by max⁡(bc[T],gs)\max(bc[T], gs), ensuring the shift is safe and maximal based on both rules. This process repeats until i≥n−1i \geq n - 1. For illustration, consider searching P="he"P = \text{"he"} (m=2) in T="here"T = \text{"here"} : initial alignment at i=1 aligns over T[0:1]="he", matching fully and reporting position 0; next alignment at i=2 mismatches on T='r' vs P='e', with bc['r']=2 (absent in P), shifting to i=4 past the end. The bad-character heuristic shifts the pattern to align the mismatched text character with its rightmost occurrence in PP, or beyond PP if absent, preventing redundant comparisons of that character. The good-suffix heuristic, applied when the bad-character shift is insufficient, shifts to the next plausible position where the matched suffix from the end of PP can reoccur, considering border alignments in PP to avoid rechecking verified suffixes. Together, these heuristics prioritize larger skips, making the algorithm excel in scenarios with distinct patterns or large alphabets like English text, where mismatches are informative. In terms of performance, the Boyer-Moore algorithm has a worst-case time complexity of O(nm)O(nm) due to potential exhaustive backtracking in adversarial inputs, though the good-suffix rule bounds comparisons to O(n+m)O(n + m) in some refined versions. Its average-case time is O(n/m)O(n/m), as shifts often exceed 1, inspecting far fewer than nmnm characters—empirically, it inspects about n/4n/4 characters for m=5 in English prose. Space usage is O(m+∣Σ∣)O(m + |\Sigma|) for the tables, independent of nn. A notable variant is the Boyer-Moore-Horspool algorithm, proposed by Nigel Horspool, which simplifies the original by using only the bad-character rule but applying it to the text character aligned with P[m−2]P[m-2] (the position before the end) on mismatch, reducing preprocessing complexity while retaining much of the efficiency for practical texts. This tradeoff makes it easier to implement and nearly as fast in average cases, with the same O(nm)O(nm) worst-case time.

Rabin-Karp Algorithm

The Rabin-Karp algorithm is a probabilistic string-searching method that uses hashing to identify potential matches of a pattern string PP of length mm within a text string TT of length nn, where typically n≫mn \gg m. Introduced by M. Karp and in 1987, it computes hash values for PP and sliding windows of TT to filter candidates quickly, followed by exact character-by-character verification to resolve any hash collisions. This approach achieves linear-time performance in the average case by leveraging a mechanism that avoids recomputing hashes from scratch for each substring. During preprocessing, the algorithm computes the hash value hPh_P of the using a rolling hash function: h_P = \left( P{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} \cdot b^{m-1} + P{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} \cdot b^{m-2} + \cdots + P[m-1] \cdot b^0 \right) \mod q Here, bb is a base (often a prime larger than the size, such as 256 for ASCII), and qq is a large prime modulus (e.g., a 64-bit prime) chosen to reduce collision probability. This step takes O(m)O(m) time. The algorithm also precomputes bm−1mod  qb^{m-1} \mod q for efficient updates. For the text, initial hashes for substrings of length mm are computed similarly, but subsequent hashes use a rolling update to slide the window by one position: hi+1=((hi−T⋅bm−1)⋅b+T[i+m])mod  qh_{i+1} = \left( (h_i - T \cdot b^{m-1}) \cdot b + T[i+m] \right) \mod q This update removes the leading character, shifts the remaining hash left by one base position, and appends the new trailing character, all in O(1)O(1) time per step. If a substring hash matches hPh_P, the algorithm performs a direct comparison of the characters to confirm the match, ensuring correctness despite possible collisions. The time complexity is O(m+n)O(m + n) in the average and expected case, as hash computations and comparisons dominate but occur linearly, with verification happening rarely due to low collision rates. In the worst case, it degrades to O(nm)O(nm) if many false positives trigger full verifications (e.g., adversarial inputs causing frequent collisions). Space usage is O(1)O(1) beyond the input strings. To further mitigate collisions, double hashing—computing two independent hashes with different bases and moduli and requiring both to match—can reduce the probability to negligible levels (e.g., below 10−1810^{-18} for 64-bit moduli). The collision probability for a single pair is at most 1/q1/q, and for n−m+1n - m + 1 comparisons, it is bounded by (n−m+1)/q(n - m + 1)/q, which is made arbitrarily small by selecting sufficiently large qq. Example
Consider searching for pattern P="314"P = "314" (m=3m=3) in text T="314159"T = "314159" (n=6n=6) using base b=10b=10 and modulus q=13q=13. Precompute hP=(3⋅102+1⋅101+4⋅100)mod  13=(300+10+4)mod  13=314mod  13=2h_P = (3 \cdot 10^2 + 1 \cdot 10^1 + 4 \cdot 10^0) \mod 13 = (300 + 10 + 4) \mod 13 = 314 \mod 13 = 2. For the first T[0..2]="314"T[0..2] = "314", h0=2h_0 = 2, matching hPh_P, so verify characters (true match at position 0). Rolling to h1=((2−3⋅102mod  13)⋅10+1)mod  13=((2−1)⋅10+1)mod  13=11h_1 = ((2 - 3 \cdot 10^2 \mod 13) \cdot 10 + 1) \mod 13 = ((2 - 1) \cdot 10 + 1) \mod 13 = 11 (no match). Continue similarly for remaining positions. This illustrates efficient sliding with verification only on hash equality.

Multi-Pattern Algorithms

Aho-Corasick Algorithm

The Aho-Corasick algorithm is a dictionary-matching technique designed to find all occurrences of multiple patterns within a given text efficiently. Invented by Alfred V. Aho and Margaret J. Corasick in 1975, it constructs a finite from a set of patterns and processes the text in a single pass, making it particularly suitable for applications like bibliographic search, intrusion detection, plagiarism detection, and bioinformatics where multiple keywords must be located simultaneously. The construction begins by building a (prefix tree) from the set of patterns. Each pattern is inserted into the trie, where nodes represent prefixes of the patterns, and edges are labeled with characters from a fixed . The root node corresponds to the empty prefix, and terminal nodes mark the ends of complete patterns, often storing the matched pattern's index in an output list. This trie structure allows for O(1) transitions per character during matching, assuming a constant-sized alphabet. The total time to build the trie is linear in the sum of the patterns' lengths, denoted as m. Preprocessing extends the trie into a full automaton by adding failure links and output links using a breadth-first search (BFS) traversal starting from the root. For each node representing a string α, the failure link points to the node representing the longest proper suffix of α that is also a prefix of some pattern in the set; if no such suffix exists, it points to the root. These links are computed level by level: for a node at depth d, the failure link is found by following the parent's failure link and matching the corresponding character, ensuring the computation visits each node and edge a constant number of times for O(m) total time. Output links, or the output function, chain together matches: at a node, the outputs include not only any patterns ending there but also those from the node reached by following failure links until a pattern-ending node is found. This merging allows reporting all overlapping or embedded matches efficiently during search. The searching phase processes the text of length n by starting at the and advancing through the for each character. On a successful transition, the current state updates accordingly. On a mismatch, the algorithm follows the failure link repeatedly until a valid transition is found or the is reached, effectively skipping irrelevant prefixes. Whenever the current state (or its output chain) contains pattern endings, all associated patterns are reported as matches, along with their starting positions in the text, which can be tracked via depth or counters. This process handles overlaps naturally, as failure links propagate matches from suffixes. The total search time is O(n + z), where z is the number of matches (or output size), since each text character triggers at most a constant number of transitions amortized over the failure chains, and reporting takes time proportional to z. The is O(m), dominated by the and link structures. For example, consider patterns {"he", "she", "his", "hers"} and text "ushers". The trie has branches for "sh" → "e", "h" → "e" and "h" → "i" → "s", and "he" → "r" → "s" for "hers". Failure links connect "sh" to "h" (since "h" is a prefix), "she" fails to "he", and so on. Processing "ushers" traverses: u (root, no transition), s (to "s" of "she"), h (to "sh"), e (to "she", output "she" and via output link "he"), r (from "she" follow failure to "he", then to "her"), s (to "hers", output "hers"). This demonstrates overlap detection for "she" and "he", and the full match of "hers" without backtracking.

Suffix Tree and Suffix Array Methods

Suffix trees and suffix arrays are powerful indexing structures that preprocess a static text string TT of length nn to enable efficient single-pattern or multi-pattern searches, as well as other string processing tasks. These methods focus on organizing all suffixes of TT to allow rapid prefix matching, which directly supports pattern queries by identifying suffixes that begin with the search pattern PP of length mm. Unlike pattern-preprocessing approaches, suffix-based methods build an index on the text once, supporting arbitrary queries thereafter with minimal additional overhead. This makes them particularly suitable for large, fixed corpora such as genomic sequences or document collections, where preprocessing time is amortized over multiple searches. A suffix tree is a compressed trie representing all suffixes of TT, where each leaf corresponds to the starting position of a unique suffix, and internal nodes represent the longest common prefixes shared among groups of suffixes. Edges are labeled with substrings of TT, ensuring no node has more than one outgoing edge per character, and the tree is typically terminated with a unique end symbol to distinguish suffixes. This structure implicitly encodes the suffix relationships through shared paths from the root, allowing compact representation in linear space relative to nn. The seminal linear-time construction algorithm, known as Ukkonen's algorithm, builds the suffix tree online by incrementally adding suffixes while maintaining active points and using suffix links to avoid redundant traversals, achieving O(n)O(n) time and space complexity over a constant-sized alphabet. To search for a pattern PP in a suffix tree, traverse from the root following the edge labels that match PP; if the full path is found, the subtree rooted at the locus node (the endpoint of the matching path) contains leaves corresponding to all occurrences of PP in TT, which can be enumerated in O(m+k)O(m + k) time where kk is the number of matches. Pattern counting is straightforward by computing the size of this subtree, often precomputed during construction for O(1)O(1) queries per node. For more advanced queries like longest common extensions between suffixes, the of two leaf nodes in the tree gives the length of their shared prefix, enabling O(1)O(1) time with preprocessing. These operations highlight the suffix tree's versatility for exact matching in static texts. A is an alternative, space-efficient representation: a sorted array of integers indexing the starting positions of all suffixes of TT, effectively permuting the suffixes in without the full . To enhance search efficiency, it is often paired with the longest common prefix (LCP) array, which stores the length of the longest common prefix between every pair of consecutive suffixes in the sorted order. The LCP array can be constructed in O(n)O(n) time from the suffix array using a backward scan that compares characters while leveraging the inverse suffix array to track positions. Suffix arrays require O(n)O(n) space, similar to suffix trees, but avoid the overhead of explicit tree nodes, making them preferable in memory-constrained environments. Linear-time construction algorithms, such as the Kärkkäinen-Sanders method, achieve O(n)O(n) preprocessing by recursively sorting suffixes based on sampled ranks and merging with doubling. Searching in a suffix array typically uses binary search to find the range of suffixes prefixed by PP, comparing PP against selected suffixes in O(mlog⁡n)O(m \log n) time per query. The accelerates this by skipping unnecessary comparisons: during binary search, the LCP between the current midpoint suffix and the previous or next provides a lower bound on mismatches, allowing the search to "skip" segments of the array in amortized O(m+log⁡n)O(m + \log n) time overall. For pattern counting, the size of the matching range in the directly gives the number of occurrences, retrievable in O(m+log⁡n)O(m + \log n) time. This enhancement makes suffix arrays competitive with suffix trees for search while being simpler to implement. Both structures support key applications beyond basic searching, such as finding the longest repeated in TT, which corresponds to the deepest internal node in the with at least two descendant leaves (depth giving the length) or the maximum LCP value greater than zero in the . This can be computed in O(n)O(n) time post-construction, with applications in data compression and bioinformatics for identifying tandem repeats. Pattern counting extends to multiple patterns by querying each independently, enabling efficient indexing for static text corpora. Overall, and provide O(n)O(n) preprocessing, O(m+log⁡n)O(m + \log n) query times, and O(n)O(n) space, balancing efficiency and practicality for large-scale analysis.

Algorithm Classifications

By Number of Patterns

String-searching algorithms are classified based on the number of patterns they handle, which influences their preprocessing, efficiency, and applicability. Single-pattern algorithms search for one fixed PP of mm in a text TT of nn, with many achieving linear worst-case O(n+m)O(n + m) through preprocessing that avoids redundant comparisons, while others like Boyer-Moore offer sublinear average-case performance but O(nm)O(n m) worst case. Examples include the Knuth-Morris-Pratt (KMP) algorithm, which uses a prefix table to skip mismatches efficiently, and the Boyer-Moore algorithm, which leverages heuristics like bad character and good suffix rules for sublinear average-case performance. These methods require minimal preprocessing proportional only to mm, making them suitable for scenarios with a solitary query . For a finite set of kk patterns with total length mm, multi-pattern algorithms preprocess the dictionary to enable efficient simultaneous searches, often in time O(n+m+z)O(n + m + z), where zz is the number of matches reported. The Aho-Corasick algorithm constructs a with failure links to simulate multiple finite automata, allowing linear-time scanning of the text after building the structure. Similarly, the Commentz-Walter algorithm extends Boyer-Moore heuristics to multiple patterns by combining a pattern with shift tables, balancing preprocessing cost with search speed for moderate kk. Preprocessing scales with mm, which can become prohibitive for very large dictionaries, but these algorithms excel in applications like spell-checkers or intrusion detection systems where a fixed is repeatedly queried against varying texts. Algorithms handling an infinite set of patterns, typically specified by regular expressions, convert the expression into an for matching, such as an NFA via , followed by simulation on the text. This approach supports expressive queries like wildcards or alternations, but efficiency varies: NFA simulation runs in O(n⋅∣states∣)O(n \cdot |states|) time, while backtracking implementations can degrade to exponential in worst cases due to ambiguity in the pattern language. Trade-offs highlight the progression: single-pattern methods offer simplicity and low overhead but lack flexibility; finite multi-pattern techniques scale well for bounded sets yet require dictionary construction; infinite-pattern methods provide maximum expressiveness for tools like but incur higher computational costs, especially for complex expressions.

By Preprocessing Requirements

String-searching algorithms are classified according to their preprocessing requirements, which specify whether and how the (of length mm), the text (of length nn), or both are prepared before the search phase begins. This categorization emphasizes trade-offs in initial computation time, auxiliary space, and search efficiency, influencing suitability for scenarios—where the text arrives incrementally without full prior access—and offline scenarios, where the entire text is available upfront. Algorithms with no preprocessing, such as the naive string-matching method, incur O(1)O(1) setup time, shifting the full computational cost to the search phase, which can reach O(nm)O(nm) in the worst case. The naive approach compares the directly against every of the text starting at each position, without any auxiliary data structures. In contrast, pattern-preprocessing-only algorithms, exemplified by the Knuth-Morris-Pratt (KMP) and Boyer-Moore methods, require O(m)O(m) preprocessing time on the to construct tables that enable O(n+m)O(n + m) overall . The KMP algorithm builds a failure function (or prefix table) that identifies the longest proper prefix matching a of the , allowing skips over mismatched portions during search. The Boyer-Moore algorithm preprocesses shift tables based on bad-character and good-suffix heuristics, often skipping multiple characters per mismatch for sublinear average-case performance. The Rabin-Karp algorithm also falls here, with O(m)O(m) preprocessing to compute a hash value for the , enabling efficient comparisons during the O(n)O(n) search phase. Text-preprocessing-only approaches, such as those using trees or arrays, demand O(n)O(n) build time on the text to support rapid pattern queries, typically in O(m+log⁡n)O(m + \log n) time, but assume a static text since modifications require rebuilding the structure. trees compress all suffixes into a trie-like form, facilitating longest common prefix queries essential for matching; the linear-time construction was achieved by Ukkonen's , which incrementally adds suffixes while maintaining the tree. arrays, a space-efficient alternative, sort the suffixes implicitly and pair with LCP arrays for similar query speeds. Algorithms preprocessing both the pattern and text, like the Aho-Corasick and Wu-Manber methods, are designed for multi-pattern or hybrid dynamic environments, combining O(m)O(m) pattern preparation with text partitioning or indexing for overall linear-time . The Aho-Corasick algorithm constructs a of all patterns augmented with failure links akin to KMP, enabling simultaneous searches across multiple patterns in O(n+z)O(n + z) time, where zz is the number of matches. Wu-Manber extends Boyer-Moore ideas by preprocessing hash tables for pattern blocks and text shifts, partitioning the text into fixed-size windows to handle multiple patterns efficiently in large corpora. Key considerations in this involve balancing time and space: preprocessing trades initial overhead for faster searches, often requiring O(n)O(n) or more space, which suits offline applications but challenges online ones where text preprocessing must be minimal or incremental to accommodate .

By Matching Strategies

String-searching algorithms can be classified by their core matching strategies, which determine how comparisons between the pattern and text are performed during the search phase. These strategies include forward matching, which processes the text sequentially from left to right; backward matching, which starts from the right and leverages information for skips; hybrid approaches that combine techniques like hashing with verification; and -based methods that model the search as state transitions in a finite . This highlights differences in efficiency, particularly in how each strategy handles mismatches and exploits textual properties. Forward matching algorithms scan the text from left to right, comparing the starting at each position sequentially or with optimizations to avoid redundant work. The naive string-matching algorithm exemplifies this by directly comparing characters until a mismatch or full match occurs, resulting in O((n-m+1)m) worst-case , where n is the text length and m is the length. The Knuth-Morris-Pratt (KMP) algorithm improves upon this by preprocessing the to build a prefix table (or failure function) that indicates the longest proper prefix which is also a , allowing the search to shift the pattern by more than one position on mismatches without re-examining previously matched text characters. This achieves O(n + m) time in both average and worst cases, making it suitable for scenarios requiring linear-time guarantees. Forward strategies are conceptually simple and well-suited for streaming applications where text arrives incrementally, as they process data in a single pass without needing to revisit earlier portions. Backward matching algorithms reverse the comparison direction, aligning the pattern's end with potential text positions and scanning right-to-left to identify mismatches quickly, often enabling larger skips. The Boyer-Moore algorithm is a seminal example, using two heuristics: the bad-character rule, which skips based on the rightmost occurrence of a mismatching text character in the pattern, and the good-suffix rule, which shifts using information about matched suffixes. This approach yields average-case O(n/m) time for large patterns and alphabets, though worst-case remains O(nm). Backward strategies excel in practice on texts like English, where large alphabets and low character frequencies allow frequent long skips, outperforming forward methods by factors of 2 to 10 in benchmarks on such data. Hybrid strategies integrate multiple techniques to balance preprocessing, comparison speed, and verification. The Rabin-Karp algorithm hashes the pattern and rolling hashes of text windows forward, comparing hashes first to filter candidates before exact character verification, achieving average O(n + m) time but O(nm) worst-case due to hash collisions. Bit-parallel algorithms like Shift-Or enhance forward matching by simulating multiple comparisons using bitwise operations on word-sized registers, effectively processing up to 64 (or more) characters per step on modern hardware for small patterns, with O(n⋅(m/w)+m)O(n \cdot (m / w) + m) time where ww is word size. These hybrids adapt to hardware and data characteristics, such as SIMD instructions for acceleration. Automaton-based strategies model the search as transitions in a , often deterministic for efficiency. The Aho-Corasick algorithm constructs a of patterns with failure links resembling a (DFA), allowing simultaneous matching of multiple patterns by traversing states on each text character and reporting outputs at accepting states, in O(n + z) time where z is the number of matches. While the core automaton is deterministic, implementations may simulate non-deterministic finite automata (NFAs) for space savings in multi-pattern scenarios. This approach is powerful for dictionary-based searches but requires more preprocessing than direct comparison methods. The choice of matching strategy impacts practical performance: backward methods like Boyer-Moore often dominate on random or natural-language texts due to skip heuristics, while forward and automaton-based ones provide robustness for worst-case or multi-pattern needs, and hybrids offer versatility across applications.

Advanced and Specialized Variants

Real-Time String Matching

Real-time string matching, also known as string matching, operates under the model where the text arrives incrementally from left to right, and the algorithm must process each character as it becomes available, reporting any matches immediately without lookahead into future characters. This contrasts with offline algorithms that require the entire text for preprocessing, as online variants maintain a or failure function to track partial matches in constant space. The primary goal is to achieve amortized O(1) time per input character while using O(m) space for a pattern of length m, ensuring suitability for where the text length n can be arbitrarily large and unbounded. For single-pattern matching, the Knuth-Morris-Pratt (KMP) algorithm serves as a foundational adaptation for real-time scenarios, processing the stream via its prefix table (failure function) to skip redundant comparisons and maintain the current matching state after each character. The Morris-Pratt variant similarly employs a preprocessing step to compute shift values, enabling efficient online advancement through the text without beyond the current position. These adaptations ensure linear total time O(n + m) for the entire stream, with no global data structures beyond the pattern itself. In multi-pattern settings, the Aho-Corasick automaton extends to streaming by constructing a of all patterns upfront and traversing it character-by-character on the input stream, using output links to report overlapping matches lazily as they complete. For bounded-buffer environments like network processing, the Wu-Manber adapts by grouping patterns into blocks and using hash tables for quick shifts, allowing real-time inspection without full text buffering. These methods maintain O(n total time across patterns of total length z, with preprocessing O(z |Σ|) for Aho-Corasick and O(z) for Wu-Manber, that remains fixed during streaming. Key challenges in real-time string matching include enforcing constant space to handle infinite streams and achieving O(1) amortized processing per character to meet throughput demands, particularly in resource-constrained systems. Unlike offline approaches with global preprocessing, online variants forgo extensive indexing to avoid delays, prioritizing immediate responsiveness. A prominent application is network packet inspection, where algorithms like Aho-Corasick detect intrusion signatures in arriving payloads for real-time threat mitigation. Similarly, in real-time log analysis, these techniques scan streaming logs for keywords such as error indicators, enabling instant alerting without batching.

Approximate and Fuzzy Matching

, also known as fuzzy string matching, addresses the challenge of finding occurrences of a pattern PP of mm in a text TT of nn, where the match allows for a limited number of errors such as substitutions, insertions, or deletions, typically measured by the Levenshtein d(T[i..i+m−1],P)≤kd(T[i..i+m-1], P) \leq k for some small integer kk. This problem extends exact string matching by tolerating imperfections, which is essential when dealing with noisy data, typographical errors, or biological variations. The foundational approach to computing the between two strings relies on dynamic programming, as formalized in the Wagner-Fischer algorithm, which constructs a matrix to calculate the minimum number of edit operations required to transform one string into the other. For approximate , this DP is applied to each potential alignment position in the text, resulting in a of O(nm)O(nm) to find all occurrences with at most kk, though early termination can prune computations when distances exceed kk. Space usage can be optimized to O(m)O(m) by retaining only two rows of the matrix at a time. To improve efficiency when kk is small compared to mm, banded dynamic programming restricts computations to a diagonal band of width proportional to kk around the of the DP matrix, reducing the time complexity to approximately O(nk+mk)O(nk + mk), or O(nk)O(nk) in practice for fixed mm and small kk. This technique is particularly effective for long texts, as it avoids unnecessary calculations far from potential alignments. Heuristic methods further accelerate approximate matching for specific error models. For instance, simulates the DP using bitwise operations on word-sized integers, enabling efficient computation of Levenshtein distances in time O(nmw)O\left(\frac{nm}{w}\right) in the worst case, where ww is the machine word size (typically 64 bits), and performs better for small kk by leveraging bit vectors to track multiple states simultaneously. In bioinformatics, seed-and-extend heuristics like those in the BLAST algorithm first identify short exact matches (seeds) between the pattern and text, then extend these using local alignment with scoring penalties for gaps and mismatches, approximating global edit distances while achieving sublinear time in practice for large nn. These methods find wide application in spell-checking, where dictionaries are searched for words within 1 or 2 of a query to suggest corrections, and in DNA sequence alignment, where evolutionary mutations introduce errors that must be tolerated to identify homologous regions. For example, the between "kitten" and "sitting" is 3, achieved by substituting 'k' with 's', 'e' with 'i', and inserting 'g' at the end:

kitten → sitten (substitute k→s) sitten → sittin (substitute e→i) sittin → sitting (insert g)

kitten → sitten (substitute k→s) sitten → sittin (substitute e→i) sittin → sitting (insert g)

This illustrates how approximate matching captures semantically similar but imperfect strings.

Searching with Wildcards and Don't Cares

In string searching with wildcards and don't cares, the pattern contains special symbols that provide flexibility in matching: a wildcard (often denoted as '?') matches any single character from the Σ, while a don't care symbol indicates a position in the pattern that is ignored during comparison, effectively allowing skips in the alignment without penalizing the . This variant of exact string matching is useful in scenarios requiring partial or flexible , such as querying databases with variable fields or scanning files with glob patterns, but it differs from approximate matching by enforcing correspondence except at wildcard or don't care positions. The problem is formalized as finding all occurrences of a P of length m in a text T of length n, where positions in P marked with wildcards or don't cares do not impose strict equality constraints. Automaton-based algorithms extend classical methods like the Knuth-Morris-Pratt (KMP) or Aho-Corasick automata to handle these symbols. In the KMP extension for wildcards, the failure function is modified to treat a '?' as a transition that accepts any input character, effectively creating a self-loop in the state for that position. For multi-pattern wildcard matching, the Aho-Corasick incorporates wildcard nodes with transitions to all alphabet symbols or a universal state, while don't cares are handled by bypassing comparison at those positions during state advancement. Preprocessing involves building this extended in O(m |Σ|) time for single patterns or O(total pattern length · |Σ|) for multiple, enabling linear-time scanning of the text thereafter. Bit-parallel techniques, such as variants of the Shift-And algorithm, optimize this for small alphabets by using bitvectors to represent wildcard positions: masks are precomputed where bits corresponding to '?' are set to accept any shift, allowing simultaneous simulation of multiple states via bitwise operations. The time complexity for naive implementations with k wildcards or don't cares is O(n |Σ|^k) due to branching at flexible positions, but bit-parallel and automaton optimizations reduce it to O(n + occ) worst-case, where occ is the number of matches, assuming word size at least |Σ|. For example, the pattern P = "a?c?" matches the substring "abcx" in text T because the first '?' aligns with 'b' (any character) and the second with 'x' (any), while 'a' and 'c' match exactly; don't cares would skip comparison at those indices entirely. These methods find applications in file system globbing (e.g., matching "*.txt" via wildcards for any prefix) and lightweight regular expression engines, where full regex complexity is unnecessary. Recent advancements in compressed data structures, such as wavelet trees adapted for wildcard queries, achieve space usage of O(n log |Σ| / log n) bits while supporting O(|P| log n + occ) query time, addressing storage challenges in large repetitive texts like genomic data.

References

  1. https://algs4.cs.princeton.edu/53substring/
  2. https://www.cs.colostate.edu/~rmm/dawgs.pdf
  3. https://www.shs-conferences.org/articles/shsconf/pdf/2022/14/shsconf_stehf2022_03018.pdf
  4. https://www.cs.jhu.edu/~misha/Spring23/Knuth77.pdf
  5. https://www.cs.utexas.edu/~moore/publications/fstrpos.pdf
  6. https://web.cs.ucdavis.edu/~gusfield/cs122f10/znote.pdf
  7. https://www.cs.purdue.edu/homes/spa/papers/lothaire.pdf
  8. https://ocw.mit.edu/courses/18-417-introduction-to-computational-molecular-biology-fall-2004/f4800301e44750bc2bd5d4fb53f3f8de_lecture_10.pdf
  9. https://cs.brown.edu/courses/cs295-11/2007/fast.pdf
  10. https://dl.acm.org/doi/10.1145/3707292.3707337
  11. https://dl.acm.org/doi/10.1145/74697.74700
  12. https://dl.acm.org/doi/10.1145/360825.360855
  13. https://dl.acm.org/doi/10.1145/359842.359859
  14. https://dl.acm.org/doi/10.1109/SWAT.1973.13
  15. https://link.springer.com/article/10.1007/BF01206331
  16. https://www.cambridge.org/core/books/algorithms-on-strings-trees-and-sequences/F0B095049C7E6EF5356F0A26686C20D3
  17. https://dl.acm.org/doi/10.1145/1080695.1069981
  18. https://icarus.cs.weber.edu/~dab/cs1410/textbook/8.Strings/c_string.html
  19. https://docs.oracle.com/javase/8/docs/api/java/lang/String.html
  20. https://docs.python.org/3/library/stdtypes.html#str
  21. https://www.unicode.org/reports/tr17/
  22. https://dl.acm.org/doi/pdf/10.3115/993268.993378
  23. https://www.cs.tufts.edu/comp/150GEN/classpages/exact.html
  24. https://rafalab.dfci.harvard.edu/dsbook/string-processing.html
  25. https://people.eecs.berkeley.edu/~jrs/4/lec/26
  26. https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf
  27. https://dl.acm.org/doi/pdf/10.1145/1952998.1953002
  28. https://webpages.charlotte.edu/ras/courses/StringMatching-2.pdf
  29. https://www.researchgate.net/publication/234825482_Algorithms_for_string_searching
  30. http://i.stanford.edu/pub/cstr/reports/cs/tr/77/629/CS-TR-77-629.pdf
  31. http://www-igm.univ-mlv.fr/~lecroq/articles/spe95.pdf
  32. https://www.cs.utexas.edu/~moore/publications/sustik-moore.pdf
  33. https://web.cs.ucdavis.edu/~gusfield/cs224f09/bnotes.pdf
  34. https://www.cs.tufts.edu/comp/150GEN/classpages/BoyerMoore.html
  35. Searching for occurrences of a substring in a text is a common operation familiar to anyone who uses a text editor, word processor, or web browser.
  36. Dec 21, 2017 · This website is a great resource for exact string searching algorithms. High-performance pattern matching in Java for general string searching.
  37. https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1688&context=ecetr
  38. http://www.cs.emory.edu/~cheung/Courses/253/Syllabus/Text/Matching-Boyer-Moore2.html
  39. https://ics.uci.edu/~goodrich/teach/cs165/notes/PatternMatch.pdf
  40. https://www.scirp.org/reference/referencespapers?referenceid=2829152
  41. https://dmice.ohsu.edu/bedricks/courses/cs655/pdf/readings/gusfield_chap_3.pdf
  42. https://arxiv.org/pdf/1811.10498.pdf
  43. https://cr.yp.to/bib/1975/aho.pdf
  44. https://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Small02.pdf
  45. https://epubs.siam.org/doi/10.1137/0222058
  46. https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
  47. https://www.cs.helsinki.fi/juha.karkkainen/opetus/13s/spa/lecture10.pdf
  48. https://link.springer.com/chapter/10.1007/3-540-48194-X_17
  49. https://www.cs.helsinki.fi/juha.karkkainen/publications/jacm05-revised.pdf
  50. https://cp-algorithms.com/string/suffix-array.html
  51. https://www.geeksforgeeks.org/dsa/suffix-tree-application-3-longest-repeated-substring/
  52. http://www-igm.univ-mlv.fr/~lecroq/string/
  53. http://www.stringology.org/athens/TextSearchingAlgorithms/tsa-lectures-1.pdf
  54. http://www.stringology.org/papers/Antos-PhD_thesis-2010.pdf
  55. https://www.dmi.unict.it/faro/papers/journal/faroJ13.pdf
  56. https://www.geeksforgeeks.org/dsa/rabin-karp-algorithm-for-pattern-searching/
  57. https://www.cs.arizona.edu/sites/default/files/TR94-17.pdf
  58. http://www-igm.univ-mlv.fr/~lecroq/string.pdf
  59. https://dl.acm.org/doi/10.1145/2431211.2431212
  60. https://users.dcc.uchile.cl/~gnavarro/ps/acmcs01.1.pdf
  61. https://nymity.ch/sybilhunting/pdf/Levenshtein1966a.pdf
  62. http://www.gersteinlab.org/courses/452/09-spring/pdf/Myers.pdf
  63. https://www.biostat.wisc.edu/bmi576/papers/blast.pdf
  64. https://www.cambridge.org/core/books/flexible-pattern-matching-in-strings/D610D1F9C4744A864D73904B24EF602B
  65. https://www.jsoftware.us/vol6/jsw0612-7.pdf
  66. http://www.ittc.ku.edu/~jsv/Papers/LNV14.WildcardPatternMatching.pdf
  67. https://arxiv.org/pdf/1407.0950
Add your contribution
Related Hubs
Contribute something
User Avatar
No comments yet.