String, Sequence and Text Algorithms

Introduction

Strings and sequences are fundamental representations of information. Source code, DNA, protein sequences, log records, web documents, search queries, network signatures and natural-language messages can all be treated as sequences over an alphabet. The alphabet may be small, such as {A, C, G, T} in DNA, or extremely large and variable, as in Unicode text.

String algorithms address the efficient storage, comparison, indexing, searching and transformation of sequences. Their importance is amplified by modern data volumes: a search engine may index billions of documents; a cybersecurity system may inspect high-speed streams for signatures; and a bioinformatics pipeline may compare genomes containing billions of bases. A naive algorithm that scans every possible position or compares every pair of sequences can become unusable at scale.

This chapter develops the principal data structures and algorithms used for text processing: tries, suffix trees and suffix arrays, rolling hashes, exact and approximate pattern matching, edit distance, longest common subsequences and compression. It also evaluates their engineering trade-offs and illustrates their use in an applied search scenario.

Learning Objectives

After completing this chapter, a student should be able to:

1. Model strings, sequences, alphabets and substrings precisely.
2. Select and implement tries, suffix arrays and related indexes.
3. Explain rolling hashes and the probabilistic nature of hash-based matching.
4. Compare naive, KMP, Boyer–Moore and Rabin–Karp pattern matching.
5. Compute and interpret edit distance and longest common subsequence.
6. Explain prefix, dictionary and statistical compression approaches.
7. Evaluate time, space, accuracy, update and governance requirements in practical systems.

1. Formal Foundations

Let an alphabet be a finite set Σ. A string, or sequence, is an ordered tuple of symbols from Σ. If a string S has length n, it is written as S[0…n−1]. The empty string is denoted ε and has length zero. A prefix begins at position zero; a suffix ends at position n−1; a substring is a contiguous portion of a string; and a subsequence preserves order but need not be contiguous.

For example, for S = BANANA, BAN is a prefix, ANA is a substring, ANA is also a subsequence, and NAA is not a subsequence because the final A would occur before the second A selected in order. A pattern P of length m occurs in a text T of length n at position i when T[i+j] = P[j] for every 0 ≤ j < m.

The central complexity measures are:

• n: text length;
• m: pattern length;
• σ = |Σ|: alphabet size;
• k: number of requested occurrences or edits;
• z: number of phrases or matches in a compressed representation.

Unless stated otherwise, character comparison and array access are assumed to take constant time. For Unicode, this assumption requires care: a user-perceived character may consist of multiple code points, and normalization can change the byte representation without changing visual meaning.

2. Tries: Prefix-Oriented Indexing

A trie is a rooted tree in which each edge represents a symbol and the path from the root to a marked node represents a stored string. The name derives from retrieval. Unlike a binary search tree, a trie’s search time depends primarily on the length of the query, not on the number of stored strings.

For a set of strings with maximum length L, exact lookup takes O(L) time. Insertion and deletion also take O(L), provided child access is constant time. A trie can support prefix queries: after following a prefix of length p, a traversal of the resulting subtree enumerates all matching completions.

Representation choices

A node may store children using:

• a fixed array of size σ, giving fast access but potentially high memory consumption;
• a balanced map, giving approximately O(log d) child access when a node has degree d;
• a hash table, giving expected O(1) access but additional overhead and weaker ordering;
• a compressed representation, such as a radix tree, which merges chains of single-child nodes.

If N characters are stored in an uncompressed trie, the number of nodes is at most N + 1, but the memory cost can be much greater when every node contains a large child array. A radix tree reduces structural overhead by storing labels on edges rather than one character per edge.

Tries are effective for autocomplete, routing tables, dictionaries, spell-checking, IP longest-prefix matching and token vocabularies. They are less suitable when the main operation is arbitrary substring search, because they naturally index prefixes rather than all suffixes.

3. Suffix Trees and Suffix Arrays

A suffix index supports queries for substrings by organizing all suffixes of a text. A suffix tree is a compressed trie of all suffixes. For a text of length n, append a unique terminal symbol $ that is not in the alphabet. For BANANA$, the suffixes are:

BANANA$, ANANA$, NANA$, ANA$, NA$, A$, $.

In a suffix tree, every suffix ends at a distinct leaf. A pattern search follows edge labels until either the pattern is exhausted or a mismatch occurs. With suitable representation, a pattern of length m can be searched in O(m + occ) time, where occ is the number of reported occurrences. Construction can be linear in n, but sophisticated algorithms such as Ukkonen’s require careful implementation, and memory overhead is often substantial.

A suffix array is a sorted array of the starting positions of all suffixes. For BANANA$, the lexicographically sorted suffixes are:

Thus the suffix array is [6, 5, 3, 1, 0, 4, 2]. A pattern’s occurrences form a contiguous interval in this sorted order. Two binary searches identify the lower and upper boundaries of that interval. Each comparison may inspect up to m symbols, so a direct implementation takes O(m log n + occ) time; longest-common-prefix information and optimized comparisons can reduce repeated work.

The LCP array stores the longest common prefix between adjacent suffixes in suffix-array order. For example, the LCP of A$ and ANA$ is one because their common prefix is A. Suffix arrays are usually more compact than suffix trees and are widely used in full-text indexing, genome analysis, plagiarism detection and compressed text indexes.

Suffix-array construction

A simple construction sorts suffixes using a comparison sort and may require O(n log n) comparisons, with each comparison potentially costing O(n). Prefix-doubling algorithms improve practical performance by sorting suffixes according to ranks of blocks of length 1, 2, 4, …. Linear-time construction algorithms exist, but engineering choices often favor prefix doubling because of implementation simplicity and predictable memory behavior.

Comparison of indexes

4. Rolling Hashes and Exact Matching

A rolling hash maintains a fingerprint of a fixed-length window while the window moves through a text. A common polynomial hash for a sequence x₀x₁…x_{m−1} is:

Here, b is a chosen base, q is a modulus, and each xᵢ is a numeric encoding of a symbol. For a window T[i…i+m−1], the outgoing symbol can be removed and the incoming symbol added:

The formula assumes the same window length m, consistent symbol encoding and arithmetic modulo q. The value b^{m−1} mod q is precomputed. Modular arithmetic prevents unbounded integer growth.

Rabin–Karp computes the pattern hash and each text-window hash. A hash match is only a candidate: distinct strings can collide. Therefore, an exact implementation must verify the symbols after a hash match. With a well-distributed hash, expected running time is O(n + m + occ); the worst case can be O(nm) if many collisions or verifications occur.

Double hashing uses two independent moduli or hash constructions. The probability of an accidental collision is reduced, but not mathematically eliminated unless verification is performed. In security-sensitive systems, adversaries may deliberately construct collisions, so cryptographic hashes or direct verification may be required. A rolling hash is a fast indexing fingerprint, not automatically a cryptographic integrity mechanism.

5. Pattern-Matching Algorithms

Naive matching

The naive algorithm aligns the pattern at every text position and compares characters from left to right. Its worst-case complexity is O((n−m+1)m), usually written O(nm), with O(1) auxiliary space. It remains useful for short patterns, small inputs and reference implementations.

Knuth–Morris–Pratt

KMP avoids rechecking text characters after a mismatch. It constructs a failure function, often called the prefix-function or LPS array, where LPS[j] is the length of the longest proper prefix of P[0…j] that is also a suffix of it. After a mismatch at pattern position j, the algorithm shifts to LPS[j−1] rather than returning to zero.

KMP preprocessing takes O(m) time and O(m) space. Searching takes O(n), so total complexity is O(n + m). Its guarantee is valuable in systems that require predictable latency, such as intrusion detection and streaming text filters.

Boyer–Moore and its variants

Boyer–Moore compares the pattern from right to left and uses mismatch information to skip alignments. The bad-character rule shifts the pattern according to the last occurrence of the mismatching text symbol; the good-suffix rule exploits matched suffixes. In typical natural-language text it can be very fast, often examining substantially fewer than n characters, although basic forms have non-linear worst cases. Variants such as the Galil rule and tuned bad-character tables improve performance. For small alphabets or very short patterns, its advantage may diminish.

Choosing an algorithm

6. Edit Distance

Edit distance measures the minimum cost of transforming one string into another. The Levenshtein distance permits insertion, deletion and substitution, commonly with unit cost. Let D[i,j] be the distance between prefixes X[0…i−1] and Y[0…j−1]. The boundary conditions are:

For i > 0 and j > 0:

where c = 0 if X[i−1] = Y[j−1], and c = 1 otherwise. The three alternatives represent deletion, insertion and substitution. This dynamic program has O(|X||Y|) time and space in its full-table form. Since each row depends only on the preceding row, space can be reduced to O(min(|X|, |Y|)) when only the distance is required.

Worked example

For X = CATS and Y = CUTS, the optimal transformation substitutes A with U, giving distance 1. A dynamic-programming table would have dimensions 5 × 5, including the empty-prefix row and column. The diagonal transition at the differing character costs one, while matching C, T and S costs zero.

Weighted edit distance assigns different costs to operations. For example, a substitution between visually similar characters may cost less than a substitution between unrelated characters. In computational linguistics, insertion, deletion and substitution costs can be learned from observed errors. A thresholded algorithm may stop or restrict computation when only distances at most k are relevant; banded dynamic programming then examines roughly O(k min(n,m)) cells under appropriate assumptions.

Applications include spell correction, record linkage, OCR correction, DNA sequence comparison and fuzzy deduplication. Edit distance is not a universal measure of semantic similarity: “car” and “automobile” have a large character distance despite similar meaning.

7. Longest Common Subsequence

A common subsequence preserves order but does not require contiguity. The LCS problem seeks a longest sequence appearing as a subsequence of both X and Y. Let L[i,j] be the LCS length of prefixes of lengths i and j:

The recurrence is justified because equal final symbols can extend an optimal solution, while unequal final symbols require excluding at least one of them from an optimal solution. The standard algorithm takes O(nm) time and O(nm) space, reducible to O(min(n,m)) for length only. Hirschberg’s algorithm reconstructs an actual LCS in linear space while retaining quadratic time.

For X = ABCBDAB and Y = BDCABA, one LCS is BCBA, of length four; other LCSs of the same length may exist. LCS is used in file-difference tools, version control, document comparison and biological sequence analysis. It differs from edit distance: LCS focuses on preserved ordered symbols, whereas edit distance counts transformations under a specified cost model.

8. Compression Concepts

Compression reduces representation size by exploiting redundancy. Lossless compression permits exact reconstruction; lossy compression sacrifices information for a smaller representation and is generally inappropriate for source code, legal records, genomes or security evidence.

Dictionary and prefix methods

A trie-like dictionary supports prefix coding. In a prefix code, no codeword is a prefix of another, so decoding is unambiguous. Huffman coding constructs a binary prefix code from symbol frequencies. Repeatedly combining the two least-frequent nodes produces an optimal binary prefix code when symbols are coded independently and codeword lengths are integral.

If symbol i has probability pᵢ and code length lᵢ, the expected code length is:

The probabilities satisfy pᵢ ≥ 0 and ∑ᵢ pᵢ = 1. Arithmetic coding represents an entire sequence as a subinterval of [0,1), often achieving performance closer to the entropy of the source than a symbol-by-symbol prefix code.

LZ77 replaces repeated substrings with references to earlier text, commonly represented by a distance–length pair. LZ78 and dictionary variants build explicit phrase dictionaries. These methods are useful for general files because they exploit repetition without requiring a fixed statistical model.

Burrows–Wheeler transform and compressed indexes

The Burrows–Wheeler transform (BWT) reorders a string so that symbols with similar contexts become adjacent. It is reversible when sufficient metadata, including a primary index or equivalent marker, is retained. BWT itself is not compression; it makes subsequent run-length, move-to-front and entropy coding effective. The FM-index uses the BWT and rank data structures to perform backward pattern search in compressed space, making it important in genome indexing and large text collections.

Compression creates trade-offs. It can reduce storage and I/O, but decompression consumes CPU and may complicate random access, updates, debugging and legal preservation. A compressed index should therefore be evaluated by end-to-end latency and total resource use, not compressed size alone.

9. Integrated Application: Search and Threat-Intelligence Platform

The following is an illustrative case. A security company maintains millions of threat reports, malware strings, URLs and packet signatures. Analysts need prefix completion for queries, exact phrase search, approximate matching of obfuscated indicators and rapid repeated search over a mostly static corpus.

Background and problem

A single data structure cannot optimize every operation. Prefix queries require low-latency completion; exact phrase queries require substring indexes; approximate matching must tolerate small mutations; and streaming detection requires predictable processing time. The corpus also contains personal data in incident reports, creating retention and access-control obligations.

Analysis and solution

A radix trie stores normalized query terms and malware-family names. Edge compression reduces memory compared with a character-per-node trie. A suffix array with an LCP array indexes the static report corpus. Search first uses binary search to find the suffix interval matching a phrase and then maps suffix positions to documents. Frequently requested phrases are cached.

KMP is used for deterministic scanning of live streams when signatures are known and a worst-case linear guarantee is important. Rabin–Karp is used as a candidate filter for many fixed-length indicators; every candidate is verified to prevent false positives caused by collisions. A banded edit-distance computation handles indicators within a small threshold of a known signature, while policy rules prevent fuzzy matching from generating unreviewed blocks.

Documents are stored with a lossless compressor. The index retains offsets that permit controlled retrieval of compressed blocks. Unicode normalization, case-folding policy and token boundaries are defined before indexing; otherwise, a query may fail merely because equivalent text has different encodings.

Outcome and learning points

The architecture separates concerns: tries serve prefixes, suffix arrays serve static substring search, KMP supplies predictable streaming behavior, hashes reduce candidate comparisons and edit distance handles bounded variation. The principal lesson is that algorithm selection follows workload characteristics—query type, update frequency, alphabet, latency target, memory budget and error tolerance—not merely asymptotic complexity.

Security controls include encryption at rest, role-based access, audit logs, retention limits and documented handling of personal information. Approximate matching requires especially careful governance because false positives can suppress legitimate communication or trigger unjustified investigations.

10. Engineering, Ethical and Contemporary Considerations

Updates and dynamism

Suffix arrays and trees are excellent for static or append-oriented collections but expensive to update frequently. Dynamic text systems may use immutable segments, periodically rebuilt indexes and a small mutable overlay. Tries support incremental updates more naturally, although deletion and memory reclamation still require careful design.

Parallel and external-memory processing

Large indexes often exceed main memory. External sorting, memory-mapped arrays, compressed representations and block-level caching reduce I/O. Pattern matching can be parallelized across documents or independent text blocks, but matches crossing block boundaries require overlap of at least m−1 symbols for a pattern of length m.

Unicode and normalization

A production system must specify whether positions refer to bytes, Unicode code points or grapheme clusters. Normalization forms such as NFC and NFD can represent visually equivalent text differently. Case folding is language-sensitive. Treating all symbols as one-byte characters can produce incorrect matching, invalid offsets and security vulnerabilities such as confusable identifiers.

AI and learned indexing

Neural language models can provide semantic retrieval, but semantic similarity does not replace exact string algorithms. A robust search system often combines lexical indexes with embeddings: exact matching supports auditability and identifier lookup, while learned retrieval addresses paraphrase and meaning. Learned indexes can predict suffix or key positions, but they require fallback mechanisms, monitoring and retraining when the data distribution changes.

Best practices

1. Define the text unit—byte, code point, token or grapheme—before designing algorithms.
2. State whether matching is exact, normalized, case-insensitive or approximate.
3. Separate candidate generation from exact verification when hashes or filters are used.
4. Measure tail latency, memory, build time, update cost and false-positive rate.
5. Use adversarial testing for hash collisions and pathological patterns.
6. Preserve provenance and offsets when transforming or compressing text.
7. Apply access control, minimization and retention rules to indexed content.
8. Benchmark on representative multilingual and domain-specific workloads.

Chapter Summary

String and sequence algorithms provide the foundations of search, comparison, indexing and compression. Tries organize dictionaries by prefixes and support efficient completion. Suffix trees and suffix arrays organize suffixes to answer repeated substring queries, with suffix arrays generally offering a useful compactness–performance balance. Rolling hashes update window fingerprints efficiently but require collision awareness and, for exactness, verification.

Naive matching is simple; KMP provides a linear worst-case guarantee; Boyer–Moore often performs well on ordinary text; and Rabin–Karp is useful for hash-based candidate filtering. Edit distance models minimum-cost transformations, while LCS identifies the longest order-preserving shared subsequence. Compression methods include prefix codes, Huffman coding, arithmetic coding, dictionary schemes and the BWT/FM-index family. Each technique involves trade-offs among time, space, update cost, accuracy, interpretability and governance.

Professional systems combine multiple structures according to workload. Correct Unicode handling, collision resistance, reproducible normalization, privacy protection and empirical benchmarking are as important as asymptotic complexity.

Key Terms

Alphabet: A finite set of symbols from which strings are formed.

Substring: A contiguous portion of a string.

Subsequence: An order-preserving selection of symbols that need not be contiguous.

Prefix: A substring beginning at the first position.

Suffix: A substring ending at the final position.

Trie: A rooted prefix tree representing a set of strings.

Radix tree: A compressed trie that stores strings or substrings on edges.

Suffix tree: A compressed trie of all suffixes of a text.

Suffix array: The lexicographically sorted array of suffix starting positions.

LCP array: An array of longest common-prefix lengths between adjacent sorted suffixes.

Rolling hash: A hash updated efficiently as a fixed-size window moves.

Collision: An event in which distinct strings produce the same hash value.

KMP: A linear-time pattern-matching algorithm using prefix or failure information.

Boyer–Moore: A right-to-left pattern matcher using shift heuristics.

Edit distance: Minimum transformation cost between two strings under specified operations.

LCS: Longest common subsequence of two sequences.

Prefix code: A code in which no codeword is a prefix of another.

Huffman coding: Frequency-based construction of an optimal binary prefix code.

BWT: Burrows–Wheeler transform, a reversible context-grouping permutation.

FM-index: A compressed text index supporting backward search using the BWT.

Review Questions

5 Short Answer Questions

1. Distinguish a substring from a subsequence and give one example of each.
2. Why can a trie answer prefix queries efficiently?
3. What information is stored in an LCP array?
4. Why must a Rabin–Karp hash match normally be verified?
5. State the three operations in unit-cost Levenshtein distance.

5 Long Answer Questions

1. Explain suffix trees and suffix arrays, including their construction ideas, query behavior and engineering trade-offs.
2. Derive the edit-distance recurrence and discuss its time and space complexity.
3. Compare naive matching, KMP, Boyer–Moore and Rabin–Karp for different workloads.
4. Explain how Huffman coding, dictionary compression and the BWT exploit different kinds of redundancy.
5. Design a text-search architecture for a multilingual, mostly static document collection and justify each index.

3 Analytical / Application Questions

1. A system must scan a high-speed stream with a guaranteed linear worst-case bound and no preprocessing reuse across patterns. Which matching strategy or combination would you choose, and why?
2. A genome database receives millions of substring queries but is rebuilt only weekly. Compare a suffix array, suffix tree and FM-index for this workload, considering memory, construction and query requirements.
3. A fuzzy security filter uses a single rolling hash and automatically blocks every hash match. Identify the technical risk and propose a safer processing and governance design.

Multiple Choice Questions with Answers

Question 1

Which operation is naturally supported by a trie in time proportional to the query length, excluding output enumeration?

A. Prefix lookup

B. Arbitrary substring lookup

C. All-pairs edit distance

D. Suffix sorting

Correct Answer: A. Prefix lookup

Question 2

For a text of length n and pattern of length m, what is the total worst-case time complexity of KMP matching, including preprocessing?

A. O(nm)

B. O(n + m)

C. O(m log n)

D. O(n² + m²)

Correct Answer: B. O(n + m)

Question 3

Why does Rabin–Karp require verification after equal hash values are found?

A. Hashes cannot be computed incrementally

B. The pattern length is unknown

C. Different strings can collide

D. Binary search is mandatory

Correct Answer: C. Different strings can collide

Question 4

What does the LCP value between two adjacent suffixes represent?

A. Their longest common suffix

B. Their longest common prefix

C. The number of occurrences of the pattern

D. The distance between their starting positions

Correct Answer: B. Their longest common prefix

Question 5

Using unit-cost Levenshtein distance, what is the distance between CATS and CUTS?

A. 0

B. 1

C. 2

D. 4

Correct Answer: B. 1

Question 6

Which statement correctly describes standard dynamic programming for LCS of strings of lengths n and m?

A. It requires O(n + m) time

B. It requires O(log n) space and time

C. It requires O(nm) time

D. It requires O(2^(n+m)) time

Correct Answer: C. It requires O(nm) time

Question 7

What is the primary purpose of the unique terminal symbol added when constructing a suffix index?

A. To encrypt every suffix

B. To ensure suffixes terminate distinctly

C. To reduce the alphabet to two symbols

D. To eliminate all repeated substrings

Correct Answer: B. To ensure suffixes terminate distinctly

Question 8

Which compression method constructs a binary prefix code from symbol frequencies?

A. Huffman coding

B. KMP

C. Suffix sorting

D. Edit distance

Correct Answer: A. Huffman coding

Question 9

A suffix array for a mostly static text is generally attractive because it is:

A. A compact ordered representation of suffixes

B. Automatically dynamic under arbitrary insertions

C. A cryptographic hash table

D. Limited to prefix queries

Correct Answer: A. A compact ordered representation of suffixes

Question 10

Which practice best prevents a rolling-hash collision from causing an incorrect exact-match result?

A. Ignore all equal hashes

B. Verify candidate windows character by character

C. Use a shorter pattern

D. Sort the text alphabetically

Correct Answer: B. Verify candidate windows character by character