String-searching algorithm

A string-searching algorithm locates occurrences of a pattern in a text, typically requiring a contiguous substring match. For text ababa and pattern aba, zero-based matches start at zero and two; overlaps count unless excluded by the specification. The direct algorithm compares the pattern at each start and can require $O(nm)$ character comparisons. The Knuth-Morris-Pratt algorithm reuses prefix information for linear total scanning work. State the alphabet, case handling and empty-pattern convention: matching bytes, Unicode code points and user-perceived characters can describe different tasks.

A longest repeated substring is a maximum-length contiguous string occurring at two distinct starting positions in a text. The occurrences may overlap unless a nonoverlap constraint is explicitly imposed. It can be found by comparing all pairs of suffixes, or by taking the maximum longest-common-prefix length of adjacent entries of a suffix array. The latter characterization concerns correctness; the time needed to build the suffix array depends on the construction algorithm.

An FM-index is a compressed text index supporting backward search through the Burrows-Wheeler transform and occurrence counts. Character rank queries locate a matching interval; sampled suffix array positions then allow the actual text positions to be recovered. Query length, number of matches and the chosen sampling density control different parts of the search cost.^[ref]

Backward search finds a query's matching interval in a suffix array by processing the query from right to left. With inclusive one-based interval $[l,r]$, prepending $c$ changes it to $[C(c)+\mathrm{Occ}(c,l-1)+1,C(c)+\mathrm{Occ}(c,r)]$. An empty interval means no match. This works through the occurrence-order property of the last-to-first mapping.^[ref]

In a sorted cyclic rotation matrix, the last-to-first mapping sends the $k$th occurrence of a character in the last column to its $k$th occurrence in the first column. For one-based rows, $\mathrm{LF}(r)=C(L_r)+\mathrm{Occ}(L_r,r)$, where $C(c)$ counts smaller characters and $\mathrm{Occ}(c,r)$ counts $c$ in the first $r$ entries of the last column. It moves a rotation's start one character backwards cyclically. Equal characters retain the lexicographic order of their following sequences, which proves the occurrence-order rule.^[ref]

The Burrows-Wheeler transform appends a unique smallest terminator to a string, sorts its cyclic rotations in lexicographic order, and records the last column. It is reversible because the first and last columns contain the same characters and the last-to-first mapping preserves the occurrence order of each character. The resulting letter arrangement supports both compression and backward search.^[ref]

A transition to a shorter suffix match after an attempted extension fails. In a Knuth-Morris-Pratt automaton, the prefix function determines the next shorter matching prefix.

The Knuth-Morris-Pratt algorithm searches for a pattern using its proper prefix-suffix overlaps. After matching $j$ characters, a mismatch replaces $j$ by the length of the longest proper border of a string for that matched prefix, repeating until the next character can extend it or $j=0$. The text index never moves backward. Precomputing prefix failure links takes $O(m)$ time; during scanning each increase in $j$ can pay for a later decrease, giving $O(n+m)$ total character work and $O(m)$ auxiliary storage. A dense Knuth-Morris-Pratt automaton is a related implementation with alphabet-dependent preprocessing and storage.^[ref]

A Knuth-Morris-Pratt automaton records how much of a fixed pattern matches the suffix of the text seen so far. State $j$ means the longest such prefix has length $j$; reading a symbol moves to the longest compatible prefix state. Reaching state $m$ reports a full length-$m$ match. For pattern aba, state two records suffix ab; reading a completes the match, while reading b falls back to state zero. A dense table for an alphabet of size $R$ uses $O(mR)$ preprocessing and storage, then constant work per text symbol.^[ref]

A border of a string is a string that is both a prefix and a suffix. A proper border is shorter than the whole string; the empty string is often included. The string ababa has proper nonempty borders a and aba. A border of length $b$ in a length-$m$ string corresponds to an overlap displacement $m-b$. The Knuth-Morris-Pratt algorithm uses a chain of such borders to decide how much of a partial match survives a mismatch, avoiding comparison of characters already known to agree.

A proper border of a string is a string prefix that is also a string suffix and is shorter than the complete string. With zero-based lengths, its length $b$ satisfies $0\le b<m$ for a length-$m$ string, if the empty string is allowed. Specify that convention when counting borders.

For ababa, the nonempty proper borders are a and aba; the complete ababa is a border of a string but not a proper one. A proper border of length $b$ allows two copies of the string to overlap with displacement $m-b$. The border aba therefore explains the shift of two between overlapping occurrences of ababa in abababa.

The prefix function stores the longest proper-border length of each prefix. For ababa, following these lengths gives $3\to 1\to 0$, listing successively shorter candidate overlaps. The Knuth-Morris-Pratt algorithm uses this chain after a mismatch, retaining a suffix already known to match rather than comparing the whole pattern again.

For a string $s$, the value ${\pi }_i$ is the length of the longest proper prefix of $s_0\cdots s_i$ that is also its suffix. Repeatedly following these lengths lists all proper borders of a string; this is the failure-link information used by the Knuth-Morris-Pratt algorithm.