String and Sequence Algorithms

Introduction and Context

Strings and sequences are among the most important data types in computing. A string is an ordered sequence of symbols, usually characters, while a sequence may contain characters, integers, biological bases, tokens, or events. Search engines locate words in documents; compilers recognize identifiers and keywords; natural language processing (NLP) compares sentences; bioinformatics aligns DNA and protein sequences; and cybersecurity systems detect suspicious event patterns.

A naive approach often compares a pattern with every possible position in a text. Although simple, this may be inefficient for large texts or repeated queries. String and sequence algorithms improve performance by exploiting structure: repeated prefixes, suffixes, symbol frequencies, hashes, or dynamic-programming subproblems.

This chapter develops pattern matching, rolling hashes, prefix functions, tries, suffix structures, subsequence algorithms, and edit distance. It also examines their complexity, implementation choices, limitations, and practical use in AI and machine-learning systems.

Learning Objectives

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

1. Explain the representation of strings and sequences and distinguish substrings, subsequences, prefixes, and suffixes.

2. Analyze naive, KMP, Rabin–Karp, and trie-based search methods.

3. Construct and use a prefix function for efficient pattern matching.

4. Explain rolling hashes and the role of collision verification.

5. Compare suffix arrays, suffix trees, and related indexing structures.

6. Solve longest common subsequence and edit-distance problems using dynamic programming.

7. Select suitable algorithms for search, NLP, bioinformatics, and anomaly detection.

8. Evaluate practical issues including memory, Unicode, adversarial inputs, privacy, and reproducibility.

1. Fundamental Terminology and Representations

Let a string be written as \(S=s_0s_1\ldots s_{n-1}\), where \(n=|S|\) is its length. A pattern \(P=p_0p_1\ldots p_{m-1}\) has length \(m\).

A prefix of a string is obtained from its beginning, such as `data` being a prefix of `database`. A suffix is obtained from its end, such as `base` being a suffix of `database`. A substring is a contiguous section; `tab` is a substring of `database` only if its characters occur consecutively. A subsequence preserves order but need not be contiguous; `dta` is a subsequence of `database`.

These distinctions are essential. Pattern matching normally searches for substrings, whereas sequence comparison often uses subsequences or alignments.

Character encoding

An implementation must distinguish a user-perceived character from a stored code unit. ASCII uses one byte for a restricted alphabet. UTF-8 uses one to four bytes per Unicode code point, and a visible grapheme may consist of multiple code points. Consequently, indexing a UTF-8 byte array by position does not necessarily index human-readable characters. Applications should explicitly choose whether positions and lengths refer to bytes, code points, or grapheme clusters.

Basic operations

Common operations include concatenation, indexing, slicing, comparison, insertion, deletion, and replacement. Immutable strings make sharing and reasoning easier but may cause repeated copying. Mutable buffers are efficient for construction but require careful memory management. In production systems, avoid repeated concatenation in a loop when it creates \(O(n^2)\) copying; use a builder, buffer, or list followed by a final join.

2. Exact Pattern Matching

The exact pattern-matching problem asks for all positions \(i\) such that

\[

S[i\ldots i+m-1]=P.

\]

A match is valid only when the pattern fits entirely in the text, so \(0\le i\le n-m\).

2.1 Naive matching

The naive algorithm aligns the pattern at each possible text position and compares characters from left to right. Its worst-case time complexity is \(O((n-m+1)m)\), which is \(O(nm)\), and its extra space is \(O(1)\), excluding the input.

For a random text, mismatches often occur early, so practical performance can be acceptable. However, repetitive inputs such as a text of many `a` characters and a pattern consisting mostly of `a` characters produce the worst case.

Pseudocode

```text

for i = 0 to n - m:

j = 0

while j < m and S[i+j] == P[j]:

j = j + 1

if j == m:

report i

```

2.2 Knuth–Morris–Pratt (KMP)

KMP avoids rechecking text characters after a mismatch. Its central structure is the prefix function \(\pi[q]\), where \(\pi[q]\) is the length of the longest proper prefix of \(P[0\ldots q]\) that is also a suffix of that substring. “Proper” means shorter than the entire substring.

For `ababaca`, the prefix-function values are:

```text

pattern: a b a b a c a

pi: 0 0 1 2 3 0 1

```

For example, at index 4, `ababa` has longest proper prefix-suffix `aba`, of length 3.

The prefix function can be computed in \(O(m)\) time:

```text

pi[0] = 0

j = 0

for i = 1 to m - 1:

while j > 0 and P[i] != P[j]:

j = pi[j-1]

if P[i] == P[j]:

j = j + 1

pi[i] = j

```

During matching, \(j\) denotes the number of pattern characters currently matched:

```text

j = 0

for i = 0 to n - 1:

while j > 0 and S[i] != P[j]:

j = pi[j-1]

if S[i] == P[j]:

j = j + 1

if j == m:

report i - m + 1

j = pi[j-1]

```

KMP runs in \(O(n+m)\) time and uses \(O(m)\) auxiliary space. It is deterministic and does not depend on a probabilistic hash assumption. It is particularly useful when a pattern is searched repeatedly or when worst-case guarantees are required.

2.3 The prefix function as a structural tool

The prefix function has uses beyond one search. It can identify borders—strings that are both prefixes and suffixes—detect periodicity, and support repeated-pattern analysis. If a string has length \(n\) and \(k=\pi[n-1]\), then a candidate smallest period is \(n-k\). It is a true period when \(n\) is divisible by \(n-k\); otherwise the string does not consist of an exact repetition of that candidate block.

3. Hash-Based Matching: Rabin–Karp

Rabin–Karp compares a hash of the pattern with hashes of text windows. A common polynomial hash for a sequence \(x_0,x_1,\ldots,x_{r-1}\) is

\[

H(x)=\left(\sum_{i=0}^{r-1} x_i b^{r-1-i}\right)\bmod M,

\]

where \(b\) is a base, \(M\) is a modulus, and symbols are mapped to integers. The values should be selected consistently, and arithmetic must avoid unintended overflow.

For adjacent windows, the outgoing symbol is removed and the incoming symbol added. If a window has length \(m\), its hash can be updated in constant time after precomputing \(b^{m-1}\bmod M\):

\[

H' = \big((H-x_{ ext{out}}b^{m-1})b+x_{ ext{in}}\big)\bmod M.

\]

A hash equality is only a candidate match. Different strings can have the same hash, called a collision, so an implementation that requires exact correctness must verify the characters after a hash match. With suitable hashing, expected time is \(O(n+m)\), but the worst case can be \(O(nm)\) if many collisions or verifications occur. Space is generally \(O(1)\) beyond the input.

Double hashing uses two independent moduli or hash schemes, greatly reducing accidental collision probability, but it is still not a mathematical substitute for verification when adversarial correctness is required. Cryptographic hashes are designed for security properties and are usually unnecessary for ordinary substring indexing; polynomial hashes are faster but should not be treated as cryptographic.

Worked example

Let the alphabet values be `a=1, b=2, c=3`, base \(b=10\), modulus \(M=101\), and window length 2. The string `ab` has hash \((1\cdot10+2)\bmod101=12\). Moving from `ab` to `bc`, remove 1, multiply the remainder by 10, and add 3:

\[

((12-1\cdot10)\cdot10+3)\bmod101=23.

\]

The update is constant time, independent of the text length.

4. Tries and Multi-Pattern Search

A trie is a rooted tree in which edges represent symbols and each root-to-node path represents a prefix. A terminal marker identifies complete stored words. Searching for a word of length \(m\) takes \(O(m)\) time, assuming child access is \(O(1)\). With a map or balanced structure for children, the cost also depends on alphabet and map operations.

Tries are appropriate for dictionaries, autocomplete, spell checking, routing tables, and lexical filtering. A dense array of children provides fast access but can consume substantial memory. Sparse maps reduce memory for large alphabets but add lookup overhead. Compressed or radix tries merge chains of single-child nodes.

A trie alone searches dictionary words against a query. For finding many patterns in a long text, the Aho–Corasick algorithm augments a trie with failure links. A failure link points to the longest suffix of the current matched path that is also a trie prefix. It is analogous to KMP’s fallback idea. After linear-time construction, scanning takes \(O(n+z)\) time, where \(z\) is the number of reported matches, apart from representation-dependent factors.

5. Suffix Structures

When many different patterns must be searched in the same text, preprocessing the text can be more efficient than preprocessing each pattern.

5.1 Suffix tree

A suffix tree is a compressed trie containing all suffixes of a text, usually with a unique terminal symbol. A pattern can be searched in \(O(m)\) time, because its characters are matched along tree edges. A suffix tree supports substring queries, occurrence reporting, longest repeated substring, and longest common substring computations. Linear construction is theoretically possible, but implementations are complex and memory-intensive.

5.2 Suffix array

A suffix array stores the starting positions of all suffixes in lexicographic order. For `banana`, the suffixes begin:

```text

0 banana

1 anana

2 nana

3 ana

4 na

5 a

```

Sorted suffixes are `a`, `ana`, `anana`, `banana`, `na`, `nana`, with starting positions `[5,3,1,0,4,2]`. A pattern is located using binary search over suffixes. Comparing a pattern with a suffix may take \(O(m)\), giving a straightforward \(O(m\log n)\) search; longest-common-prefix enhancements can improve repeated-query performance. The suffix array uses \(O(n)\) positions, usually less memory than a suffix tree. An LCP (longest common prefix) array records the common-prefix length of adjacent sorted suffixes and supports advanced range queries.

Suffix arrays are widely used in full-text indexing and bioinformatics. Their trade-off is preprocessing time, implementation complexity, and storage of auxiliary arrays.

6. Subsequences and Dynamic Programming

6.1 Longest Common Subsequence

The longest common subsequence (LCS) of strings \(X\) and \(Y\) is the longest sequence that appears in both while preserving order. It need not be contiguous.

Let \(L[i][j]\) be the LCS length of prefixes \(X[0\ldots i-1]\) and \(Y[0\ldots j-1]\). The recurrence is

\[

L[i][j]=

\begin{cases}

0,&i=0\text{ or }j=0,\\

L[i-1][j-1]+1,&X[i-1]=Y[j-1],\\

\max(L[i-1][j],L[i][j-1]),&X[i-1]\ne Y[j-1].

\end{cases}

\]

The base case represents comparison with an empty prefix. The table requires \(O(|X||Y|)\) time and space. If only the length is needed, two rows reduce space to \(O(\min(|X|,|Y|))\). Reconstructing an actual subsequence normally requires retaining decisions or using a divide-and-conquer reconstruction method.

Example. For `ABCBDAB` and `BDCABA`, the LCS length is 4; one valid LCS is `BCBA`. There may be multiple optimal subsequences.

LCS is useful for version comparison, document similarity, and biological sequence analysis, but it treats all insertions and deletions equally and does not directly model substitutions.

6.2 Edit distance

The Levenshtein distance is the minimum number of single-character insertions, deletions, and substitutions needed to transform one string into another. Let \(D[i][j]\) be the distance between prefixes of lengths \(i\) and \(j\). Then

\[

D[i][j]=\min\begin{cases}

D[i-1][j]+1 & \text{deletion},\\

D[i][j-1]+1 & \text{insertion},\\

D[i-1][j-1]+c & \text{substitution or match},

\end{cases}

\]

where \(c=0\) if the two final characters are equal and \(c=1\) otherwise. Initial conditions are \(D[i][0]=i\) and \(D[0][j]=j\), because converting a nonempty prefix to an empty one requires deletions, and vice versa.

The standard algorithm takes \(O(nm)\) time and \(O(nm)\) space, or \(O(\min(n,m))\) space for distance only. If operations have different costs, replace 1 with the relevant nonnegative cost. In bioinformatics, affine gap penalties often distinguish opening a gap from extending it, requiring additional dynamic-programming states.

Edit distance supports spell correction, fuzzy search, OCR correction, record linkage, and evaluating generated text. It is not a semantic similarity measure: `cat` and `car` have distance 1, but two sentences with small edit distance may have very different meanings.

7. Choosing an Algorithm

| Need | Suitable method | Main advantage | Main limitation |

|---|---|---|---|

| One short exact search | Naive matching | Very simple | Quadratic worst case |

| Deterministic single-pattern search | KMP | \(O(n+m)\) guarantee | Prefix preprocessing and exact matching only |

| Many candidate windows or fingerprints | Rabin–Karp | Constant-time rolling updates | Collisions and verification |

| Prefix queries and autocomplete | Trie | Time proportional to query length | Memory consumption |

| Many patterns in one text stream | Aho–Corasick | Efficient multi-pattern scan | Automaton construction and memory |

| Many queries on one static text | Suffix array/tree | Reusable text index | Preprocessing and storage |

| Ordered similarity with gaps | LCS | Preserves order | Quadratic dynamic program |

| Insert/delete/substitute similarity | Edit distance | Interpretable operations | Quadratic cost for long inputs |

The correct choice depends on whether the text or patterns are static, whether exact worst-case bounds are required, whether matches must be reported, and whether approximate similarity is intended.

8. Applications in AI and Industry

Search and information retrieval

Search systems normalize text, tokenize it, and build inverted indexes. String algorithms operate within tokenization and phrase-query components. Exact phrase matching may use positional indexes, while suffix structures support specialized substring search. Hashing can identify repeated document fragments, but collisions and normalization choices must be managed.

Natural language processing

Autocomplete commonly uses tries. Spell correction generates candidates using edit distance, keyboard-aware costs, or language-model probabilities. Token matching in rule-based NLP can use Aho–Corasick. Modern neural language models do not eliminate classical algorithms: tokenization, deduplication, alignment, evaluation, and data cleaning still depend heavily on sequence methods.

Bioinformatics

DNA consists of the alphabet \{A,C,G,T\}, while proteins use a larger amino-acid alphabet. Exact k-mer indexing, suffix arrays, and rolling hashes support sequence lookup. Alignment uses edit distance variants, but biological scoring typically assigns distinct match, mismatch, and gap costs. Large genomes make memory locality, compressed indexes, and external-memory processing important.

Anomaly detection

A system-monitoring pipeline can represent events as sequences. Frequent subsequence mining identifies normal workflows; edit distance compares a new trace with known traces; rolling hashes detect repeated or altered windows. A threshold must be calibrated on representative normal data, because a rare but legitimate workflow should not automatically be classified as malicious.

9. Illustrative Case: Detecting Suspicious API Sequences

Background

Consider a fictional cloud-service provider that records API event names such as `login`, `list`, `download`, and `delete`. Security analysts know several suspicious sequences, including credential access followed by bulk download.

Problem

The provider must scan millions of event streams and report occurrences of hundreds of suspicious patterns, including overlapping matches. Events arrive continuously, so storing every complete stream for later comparison is undesirable.

Analysis

A separate naive search for every pattern would repeatedly scan the same events. KMP would improve each individual search but would still require one scan per pattern. A trie with failure links allows all patterns to be processed in a single stream scan. Event names, rather than individual characters, are the alphabet symbols.

Approach and solution

1. Normalize event names and define whether parameters are separate symbols.

2. Insert each suspicious sequence into a trie.

3. Construct failure links using breadth-first traversal.

4. Propagate terminal outputs through failure links so that suffix patterns are also reported.

5. Scan each event stream once, following trie edges or failure links.

6. Record pattern identifier, start position, tenant, and timestamp.

7. Apply a second-stage policy model that considers frequency, user role, and context.

The automaton provides efficient candidate generation, while the policy layer prevents a purely syntactic match from becoming an automatic accusation. Logs should be access-controlled and retention-limited because event sequences can reveal sensitive user behavior.

Outcome

The organization obtains predictable multi-pattern scanning and can update the pattern dictionary without redesigning the stream processor. Evaluation uses precision, recall, detection latency, and false-positive rates. Analysts inspect sampled alerts to discover missing legitimate workflows and revise rules.

Learning points

The case demonstrates that algorithm selection depends on workload structure. Aho–Corasick is valuable because the pattern set is large and the input is streamed. It also shows that an algorithmic match is evidence for investigation, not necessarily proof of malicious intent.

10. Limitations, Governance, and Best Practices

Computational limitations

Quadratic dynamic programs become impractical for very long sequences. Use banded alignment when a small maximum distance is justified, length filters before edit distance, or approximate indexing for large-scale retrieval. Memory layout and cache behavior may dominate theoretical complexity.

Correctness limitations

Hash-based methods require collision handling. Unicode normalization can make visually identical strings compare unequal. Case folding is language-dependent; simple ASCII lowercasing is not universally correct. LCS and edit distance depend strongly on the chosen representation and cost model.

Security considerations

Attackers may construct repetitive inputs that trigger worst-case behavior or exploit hash-table weaknesses. Use bounded input sizes, timeouts, randomized hashing where appropriate, and robust library implementations. Do not use non-cryptographic hashes for password storage or authentication.

Responsible use

Sequence matching in surveillance, hiring, fraud detection, or cybersecurity can affect individuals. Systems should document thresholds, preserve audit trails, test demographic and linguistic variation, restrict access to sensitive sequences, and provide human review for consequential decisions. Training and evaluation data may contain personal or genomic information; collection and retention must follow applicable privacy laws and institutional policies.

Best practices

• Specify whether matching is byte-, code-point-, token-, or grapheme-based.
• Normalize inputs consistently and document the normalization.
• Select algorithms based on query volume, alphabet, repetition, and memory limits.
• Verify rolling-hash matches when exact correctness matters.
• Benchmark representative and adversarial inputs, not only random data.
• Separate candidate generation from semantic or policy decisions.
• Test empty strings, patterns longer than the text, repeated symbols, overlapping matches, and Unicode edge cases.
• Report both theoretical complexity and practical resource use.

11. Contemporary Developments

Compressed suffix arrays and the Burrows–Wheeler transform support compact full-text indexing. Approximate matching increasingly combines classical indexes with vector retrieval and neural reranking: symbolic algorithms provide exact or high-recall candidates, while learned models assess semantic relevance. GPU and SIMD implementations accelerate dynamic programming and batch comparisons. Streaming systems use bounded-memory sketches and windowed hashes for high-volume event data. These developments do not replace foundational algorithms; they build on their definitions, invariants, and trade-offs.

Chapter Summary

String and sequence algorithms exploit structure in ordered data. Naive matching is simple but can take quadratic time. KMP uses the prefix function to guarantee linear-time exact matching. Rabin–Karp uses rolling hashes to update window fingerprints efficiently, but collisions require care. Tries support prefix queries, and Aho–Corasick extends trie ideas to efficient multi-pattern streaming. Suffix trees and suffix arrays index a fixed text for repeated searches.

LCS measures ordered common structure, while edit distance models insertions, deletions, and substitutions through dynamic programming. Each method has assumptions about contiguity, cost, alphabet, and correctness. Applications include information retrieval, NLP, bioinformatics, log analysis, and anomaly detection. Professional use requires attention to encoding, memory, adversarial inputs, privacy, explainability, and the difference between an algorithmic match and a meaningful decision.

Key Terms

String: An ordered sequence of symbols.

Sequence: An ordered collection of elements, not necessarily characters.

Prefix: A contiguous beginning of a string.

Suffix: A contiguous ending of a string.

Substring: A contiguous portion of a string.

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

Pattern matching: Finding occurrences of a pattern in a text.

Prefix function: The longest proper prefix-suffix length for each pattern prefix.

KMP: A deterministic linear-time exact pattern-matching algorithm.

Rolling hash: A hash updated efficiently when a fixed-size window shifts.

Collision: Two distinct inputs producing the same hash value.

Trie: A tree representing prefixes of stored strings.

Aho–Corasick: A failure-link automaton for multi-pattern matching.

Suffix array: Sorted starting positions of all suffixes of a text.

Suffix tree: A compressed trie of all text suffixes.

LCP array: Values giving longest common prefixes of adjacent suffix-array suffixes.

LCS: Longest common subsequence.

Edit distance: Minimum-cost sequence of allowed insertions, deletions, and substitutions.

Dynamic programming: Solving overlapping subproblems using stored intermediate results.

Unicode normalization: A procedure for converting equivalent character representations into a consistent form.

Review Questions

Short Answer Questions

1. Distinguish a substring from a subsequence.

2. What does the prefix-function value \(\pi[i]\) represent?

3. Why must a rolling-hash match usually be verified?

4. What is the principal purpose of a trie?

5. Name the three elementary operations in Levenshtein distance.

Long Answer Questions

1. Explain the naive and KMP pattern-matching algorithms and compare their time and space complexities.

2. Describe rolling-hash computation and derive the update from one text window to the next.

3. Compare tries, suffix arrays, and suffix trees for repeated search workloads.

4. Derive the LCS recurrence and explain how a table can reconstruct an LCS.

5. Explain how edit distance can be adapted for unequal operation costs and biological gap penalties.

Analytical / Application Questions

1. A service must detect 10,000 fixed event patterns in a continuous stream. Select an algorithm and justify the choice, including how matches and memory should be handled.

2. Design a spell-correction pipeline for a multilingual application. Discuss encoding, normalization, candidate generation, distance calculation, and ranking.

3. A genome-indexing system has a static reference sequence and millions of queries. Compare a suffix array, suffix tree, and rolling-hash index, and recommend one under a strict memory constraint.

Multiple Choice Questions with Answers

Question 1

What is the worst-case time complexity of KMP pattern matching for text length n and pattern length m?

A. O(nm)

B. O(n + m)

C. O(m log n)

D. O(2^m)

Correct Answer: B. O(n + m)

Question 2

What does the prefix function π[i] store for a pattern?

A. The number of distinct symbols in the pattern prefix

B. The length of the longest proper prefix that is also a suffix

C. The position of the next mismatch in the text

D. The hash value of the pattern prefix

Correct Answer: B. The length of the longest proper prefix that is also a suffix

Question 3

Why should an exact Rabin–Karp implementation verify characters after equal hashes?

A. Hashes cannot be computed in constant time

B. A hash collision may occur

C. The pattern length may change

D. Suffixes are not ordered

Correct Answer: B. A hash collision may occur

Question 4

Which data structure is most directly suited to autocomplete by prefixes?

A. Trie

B. Stack

C. Heap

D. Disjoint-set forest

Correct Answer: A. Trie

Question 5

For a text of length n, how many suffix starting positions are stored in a suffix array?

A. n - 1

B. log n

C. n

D. n squared

Correct Answer: C. n

Question 6

Which statement about a subsequence is correct?

A. Its symbols must be contiguous

B. It must begin at index zero

C. It preserves order but need not be contiguous

D. It must have the same length as the original sequence

Correct Answer: C. It preserves order but need not be contiguous

Question 7

In standard Levenshtein distance, what is D[i][0] for a prefix of length i?

A. 0

B. 1

C. i

D. 2i

Correct Answer: C. i

Question 8

Which algorithm is designed for simultaneously searching many patterns in one text stream?

A. Aho–Corasick

B. Binary search alone

C. Selection sort

D. Floyd–Warshall

Correct Answer: A. Aho–Corasick

Question 9

If two adjacent fixed-length windows are processed by a rolling hash, which symbol is removed from the old window?

A. The incoming symbol

B. The outgoing leftmost symbol

C. The middle symbol only

D. Every symbol in the old window

Correct Answer: B. The outgoing leftmost symbol

Question 10

Which method generally reduces the space needed to compute only LCS length from O(nm) to O(min(n,m))?

A. Using two dynamic-programming rows

B. Using a suffix tree with no input

C. Replacing all symbols with hashes

D. Sorting both strings alphabetically

Correct Answer: A. Using two dynamic-programming rows