String and Sequence Algorithms

Introduction

Strings and sequences are among the most frequently processed data types in software systems. A search engine locates terms in documents, a compiler recognizes identifiers, an authentication service validates input, and a bioinformatics platform compares DNA sequences. Although a string can be stored as an array of characters, efficient processing requires algorithms that exploit structure such as repeated prefixes, suffixes, and overlapping subproblems.

This chapter develops pattern matching, rolling hashes, prefix-function methods, tries, suffix-based structures, edit distance, and longest-subsequence algorithms. It emphasizes not only how these algorithms work, but also when they should be selected and what their limitations are.

Learning Objectives

By the end of this chapter, you should be able to:

• distinguish exact, approximate, prefix, suffix, and subsequence problems;
• analyze naïve, KMP, Rabin–Karp, trie, suffix-array, and dynamic-programming methods;
• construct a prefix function and use it for linear-time pattern matching;
• explain rolling-hash collisions and suitable safeguards;
• solve edit-distance and longest-common-subsequence problems;
• select string data structures for search, validation, autocomplete, and bioinformatics;
• evaluate memory, preprocessing, Unicode, security, and implementation trade-offs.

1. Strings, Sequences, and Problem Types

A string is an ordered finite sequence of symbols drawn from an alphabet Σ. For example, BANANA is a sequence over an alphabet containing letters. A string of length n is often written s[0 … n − 1]. A substring is a contiguous portion of a string; a subsequence preserves order but may omit symbols. A prefix begins at index 0, while a suffix ends at index n − 1.

These distinctions produce different algorithmic problems:

The input model matters. A fixed small alphabet permits compact arrays; a large or multilingual alphabet often requires maps or encoded code points. In Unicode systems, a visible character may occupy multiple code units, so indexing a UTF-16 or UTF-8 representation is not always equivalent to indexing user-perceived characters.

2. Naïve Pattern Matching

Given a text T of length n and pattern P of length m, the naïve algorithm aligns P at every possible text position and compares characters from left to right. Its worst-case running time is O((n − m + 1)m), usually written O(nm). Its extra space is O(1), excluding the input.

The algorithm is often adequate when the pattern is short, the text is small, or implementation simplicity is more important than worst-case performance. Its weakness is repeated comparison. For example, a text containing many A characters and a pattern AAAAB repeatedly rechecks the same prefix.

3. Prefix Functions and KMP

The Knuth–Morris–Pratt (KMP) algorithm avoids rechecking characters by recording information about the pattern itself. Define the prefix function π[i] as the length of the longest proper prefix of P[0 … i] that is also a suffix of P[0 … i]. “Proper” means that the entire substring is excluded.

For P = ABABAC, the prefix-function values are:

The construction maintains a candidate border length j. If P[i] differs from P[j], the algorithm replaces j with π[j − 1], a shorter candidate that may still be valid. Each fallback moves to an already computed border, so construction takes O(m) time.

During matching, j records the number of pattern characters currently matched. On a mismatch, KMP falls back using π rather than moving the text pointer backward. If j reaches m, a match ends at text index i and begins at i − m + 1. The total matching time is O(n), giving O(n + m) time including preprocessing and O(m) auxiliary space.

KMP Pseudocode

prefix_function(P):
    π[0] = 0
    j = 0
    for i = 1 to m - 1:
        while j > 0 and P[i] ≠ P[j]:
            j = π[j - 1]
        if P[i] = P[j]:
            j = j + 1
        π[i] = j
    return π

KMP(T, P):
    π = prefix_function(P)
    j = 0
    for i = 0 to n - 1:
        while j > 0 and T[i] ≠ P[j]:
            j = π[j - 1]
        if T[i] = P[j]:
            j = j + 1
        if j = m:
            report i - m + 1
            j = π[j - 1]

The algorithm assumes that equality of symbols is well defined. For case-insensitive search, normalization and case folding must be specified before matching; applying them inconsistently can produce incorrect results.

4. Rolling Hashes and Rabin–Karp

Rabin–Karp represents a string by a numeric fingerprint. A common polynomial hash for symbols encoded as integers is:

Here, k is the substring length, b is a chosen base, q is a modulus, and s[i] is the numeric value of the i-th symbol. The base should be selected with respect to the alphabet and implementation; q is commonly a large prime or arithmetic is performed modulo 2⁶⁴. The hash is not proof of equality: distinct strings can collide.

For a window of length m, the next hash can be obtained without recomputing the whole window. If h is b^{m−1} mod q, outgoing symbol x and incoming symbol y are used as follows:

The subtraction is normalized into the range [0, q − 1] in modular implementations. Rabin–Karp compares hashes first and verifies actual characters whenever hashes match. With a well-distributed hash, expected time is O(n + m); worst-case time is O(nm) if many collisions occur. Space is O(1) besides the pattern and text representation.

Double hashing uses two independently parameterized hashes, making accidental collisions much less likely. Hashing must not be treated as a security mechanism unless a cryptographically suitable construction is deliberately used. Adversaries may create collision-heavy inputs or exploit predictable parameters.

5. Tries and Multi-Pattern Search

A trie is a rooted tree in which each edge represents a symbol and each root-to-node path represents a prefix. A terminal marker identifies complete stored words. Inserting or searching a word of length L takes O(L) time. Memory is O(number of stored character transitions), although a dense array at every node may waste space.

Tries support autocomplete, dictionary validation, routing prefixes, and lexicographic enumeration. A node may store frequency, permissions, or an identifier list. Implementations commonly choose among:

• fixed arrays: fast for small alphabets but memory intensive;
• hash maps: flexible for sparse transitions;
• sorted edge lists: compact and useful for ordered traversal;
• compressed or radix tries: merge single-child paths to reduce nodes.

A trie alone searches one query through dictionary prefixes. For simultaneous searching of many patterns in a text, the Aho–Corasick automaton adds failure links. A failure link points to the longest proper suffix that is also a trie prefix. With preprocessing O(total pattern length plus transitions), the text can be scanned in O(n + number of reported matches), subject to the representation of transitions.

6. Suffix-Based Structures

A suffix tree stores all suffixes of a text in a compressed trie. It supports substring queries in O(m), where m is the query length, after linear-size preprocessing in theory. In practice, suffix trees are complex and have high constant factors.

A suffix array stores the starting positions of all suffixes in lexicographic order. A related longest-common-prefix (LCP) array stores the LCP length of neighboring suffixes. A query can use binary search over suffixes. Comparing a query of length m at each binary-search step may cost O(m log n); auxiliary LCP techniques can improve this. Suffix arrays are generally easier to store and cache than suffix trees.

For text T, append a sentinel symbol smaller than every alphabet symbol and absent from the input. Without a unique sentinel, suffix boundaries can be ambiguous. Suffix structures are useful for indexing documents, finding repeated substrings, counting distinct substrings, and genome analysis. They are less suitable than tries for dynamic, prefix-oriented dictionaries because updates can be expensive.

7. Edit Distance

The Levenshtein distance between strings A and B is the minimum number of insertions, deletions, and substitutions needed to transform A into B, where each operation has unit cost. Let D[i][j] be the distance between prefixes A[0 … i − 1] and B[0 … j − 1]. The recurrence is:

where cost is 0 if A[i − 1] = B[j − 1], and 1 otherwise. Boundary conditions are D[i][0] = i and D[0][j] = j.

The recurrence is valid because an optimal final operation must be an insertion, deletion, or alignment of the two final symbols. A complete table requires O(|A||B|) time and space. Since row i depends only on row i − 1, distance alone can be computed in O(|A||B|) time and O(min(|A|, |B|)) space. Recovering an edit sequence generally requires storing decisions or using a divide-and-conquer reconstruction method.

Worked Example

For A = CAT and B = CUT, the optimal transformation substitutes A with U, so the distance is 1. The final table is:

Different applications may assign different costs. For spell correction, insertion and deletion may be more likely than substitution; for biological sequences, gap penalties and substitution matrices are often more appropriate.

8. Longest Common Subsequence

The longest common subsequence (LCS) of A and B is a longest sequence appearing in both while preserving order, not necessarily contiguously. Define L[i][j] as the LCS length for the first i and j symbols. Then:

The boundary values L[i][0] and L[0][j] are zero. The algorithm takes O(|A||B|) time and space, or linear space when only the length is required. If multiple choices have equal value, multiple valid LCSs may exist. LCS is not edit distance: it measures retained ordered symbols, whereas edit distance measures transformation cost.

Applications include source-code comparison, version merging, diff tools, and analysis of biological sequences. For very large inputs, bit-parallel methods, sparse dynamic programming, or domain-specific algorithms may be preferable.

9. Choosing an Algorithm

Performance analysis must include preprocessing, query count, alphabet size, memory locality, and update frequency. An asymptotically optimal structure may be slower for small data because of allocation overhead or poor cache behavior.

10. Applied Case: Search and Validation in a Clinical Portal

The following is an illustrative case, not a report of a specific organization.

Background and Problem

A clinical portal accepts medication names, provides autocomplete, searches documentation, and flags likely typographical errors. It must handle multilingual input, avoid false security assumptions, and protect sensitive patient data.

Analysis

Autocomplete is a prefix problem, so a normalized radix trie can store approved medication names and aliases. Documentation search is a static full-text problem, making an inverted index supplemented by token normalization more appropriate than repeatedly scanning documents. Exact phrase detection can use KMP or an indexed search engine. Typographical suggestions require weighted edit distance, but unrestricted comparison against every medication is too slow.

Approach and Solution

The system first applies documented Unicode normalization and case folding. It uses a radix trie for prefix suggestions, storing only authorized display terms and metadata. Candidate spellings are generated using a bounded edit distance, for example rejecting candidates whose distance exceeds a selected threshold. Documentation is indexed offline; queries are logged using privacy-preserving identifiers rather than raw patient text. Any hash used for deduplication is combined with collision verification when correctness matters.

Outcome

The design separates concerns: the trie provides low-latency prefix lookup, the index supports document retrieval, and dynamic programming handles a small candidate set rather than the entire dictionary. It also makes normalization, access control, retention, and audit requirements explicit.

Learning Points

1. Select a data structure according to the query type, not merely the data type.
2. Normalize before comparing, but preserve original text when display or legal records require it.
3. Treat approximate matching as a cost model, not a universal notion of similarity.
4. Correctness, privacy, and auditability are part of algorithm engineering.

11. Limitations, Security, and Contemporary Practice

String algorithms can fail when the symbol model is unspecified. Byte-wise matching may split a Unicode character; grapheme clusters such as an accented letter may have multiple representations. Systems should define whether matching operates on bytes, code points, normalized characters, or grapheme clusters.

Denial-of-service risks include quadratic regular-expression behavior, enormous trie inputs, collision-heavy hash attacks, and edit-distance computations on unbounded strings. Input length limits, timeouts, streaming, bounded candidate sets, and adversarial testing are practical safeguards.

Search and language applications increasingly combine classical structures with machine-learning retrieval and neural language models. These models improve semantic matching but do not replace exact algorithms for identifiers, legal phrases, validation, or reproducible indexing. Hybrid systems may use an inverted index or trie for candidate generation and a learned model for ranking. Their evaluation should report latency, memory, recall, precision, error cases, and fairness across languages and dialects.

Best Practices

• State whether positions refer to bytes, code points, or user-visible characters.
• Normalize consistently and document the normalization policy.
• Preprocess when many queries reuse the same pattern set or text.
• Verify hash matches instead of assuming equal hashes imply equal strings.
• Bound input sizes and candidate sets in approximate matching.
• Prefer sparse transitions or compression for large tries.
• Benchmark realistic workloads, including adversarial and multilingual data.
• Separate sensitive text from logs, telemetry, and debugging output.
• Test empty strings, repeated symbols, overlapping matches, and boundary cases.

Chapter Summary

String and sequence algorithms exploit ordering, repetition, and shared subproblems. Naïve matching is simple but can be quadratic. KMP uses the prefix function to achieve O(n + m) exact matching with predictable performance. Rabin–Karp uses rolling hashes for efficient expected matching but requires collision verification. Tries support prefix operations, while Aho–Corasick extends trie ideas to many-pattern search. Suffix arrays and related structures support static full-text indexing. Edit distance models transformations through dynamic programming, whereas LCS measures the longest ordered content shared by two sequences. Effective professional solutions also address Unicode semantics, memory, adversarial inputs, privacy, and application-specific costs.

Key Terms

String: An ordered finite sequence of symbols.

Substring: A contiguous portion of a string.

Subsequence: An order-preserving sequence that may omit symbols.

Prefix: A substring beginning at the first symbol.

Suffix: A substring ending at the final symbol.

Pattern matching: Locating occurrences of a query pattern in text.

Prefix function: The longest proper prefix that is also a suffix for each pattern prefix.

KMP: A linear-time exact pattern-matching algorithm using the prefix function.

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

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

Trie: A tree representing strings through shared prefixes.

Radix trie: A trie with compressed paths.

Failure link: A fallback link used by multi-pattern automata.

Suffix array: Lexicographically sorted starting positions of all suffixes.

LCP array: Longest-common-prefix lengths for neighboring suffixes.

Edit distance: Minimum weighted cost of transforming one string into another.

Levenshtein distance: Edit distance with unit insertion, deletion, and substitution costs.

LCS: Longest common subsequence.

Normalization: Converting equivalent textual representations to a chosen canonical form.

Review Questions

Short Answer Questions

1. What distinguishes a substring from a subsequence?
2. What does the prefix function store in KMP?
3. Why must Rabin–Karp verify matching hashes?
4. What type of query is a trie especially suited to answer?
5. State the time and space complexity of the standard edit-distance table.

Long Answer Questions

1. Explain KMP preprocessing and matching, including why its total time is linear.
2. Compare tries, suffix arrays, and inverted indexes for search applications.
3. Derive the edit-distance recurrence and explain its boundary conditions.
4. Explain rolling-hash updates and the practical use of double hashing.
5. Compare LCS and edit distance in terms of definition, recurrence, and applications.

Analytical / Application Questions

1. Design a data structure for autocomplete over ten million dictionary entries. Discuss memory, Unicode normalization, updates, and latency.
2. A service searches thousands of patterns in a continuous text stream. Choose an algorithm and justify preprocessing, output handling, and worst-case complexity.
3. A spell-checking system must compare a query with a large multilingual vocabulary. Propose a staged design using indexing, bounded edit distance, and privacy safeguards.

Multiple Choice Questions with Answers

Question 1

What does π[i] represent in the KMP prefix function?

A. The number of matches found before position i

B. The length of the longest proper prefix that is also a suffix of P[0 … i]

C. The hash value of P[0 … i]

D. The next text position to inspect

Correct Answer: B. The length of the longest proper prefix that is also a suffix of P[0 … i]

Question 2

What is the worst-case time complexity of KMP matching, including pattern preprocessing?

A. O(n + m)

B. O(nm)

C. O(m²)

D. O(log n)

Correct Answer: A. O(n + m)

Question 3

Why does Rabin–Karp compare characters after equal hash values are found?

A. Hash computation is always slower than character comparison

B. Equal hashes guarantee different strings

C. Distinct strings can produce the same hash

D. The pattern length is unknown

Correct Answer: C. Distinct strings can produce the same hash

Question 4

Which data structure is most directly suited to autocomplete?

A. Trie

B. Stack

C. Heap only

D. Disjoint-set forest

Correct Answer: A. Trie

Question 5

For strings A = CAT and B = CUT with unit edit costs, what is their Levenshtein distance?

A. 0

B. 1

C. 2

D. 3

Correct Answer: B. 1

Question 6

Which statement about a subsequence is correct?

A. Its symbols must be contiguous

B. It must contain the entire original string

C. It preserves order but may omit symbols

D. It can reorder symbols arbitrarily

Correct Answer: C. It preserves order but may omit symbols

Question 7

What is the standard time complexity of the full dynamic-programming table for LCS of strings of lengths n and m?

A. O(n + m)

B. O(log(nm))

C. O(nm)

D. O(n² + m²) only when symbols repeat

Correct Answer: C. O(nm)

Question 8

Which structure stores suffix starting positions in lexicographic order?

A. Prefix tree

B. Suffix array

C. Edit-distance matrix

D. Hash table of prefixes

Correct Answer: B. Suffix array

Question 9

What is a principal risk of using a single rolling hash as proof of string equality?

A. The text cannot contain repeated symbols

B. Hash collisions can cause false equality

C. The pattern must be sorted

D. It always requires quadratic memory

Correct Answer: B. Hash collisions can cause false equality

Question 10

Which algorithm is designed to search many patterns simultaneously in a text using trie and failure-link ideas?

A. Aho–Corasick

B. Binary insertion sort

C. Dijkstra’s algorithm

D. Floyd–Warshall

Correct Answer: A. Aho–Corasick