Cover Image

An introduction to string algorithms /

Bibliographic Details
Main Author: Kingsford, Carl (Author)
Corporate Author: EBSCOhost
Format: eBook
Language:English
Published: Princeton : Princeton University Press, 2026.
Subjects:
Computer algorithms.
Algorithmes.
algorithms.
Computer algorithms
Electronic books.
Online Access:Connect to the full text of this electronic book
Table of Contents:
  • Cover
  • Contents
  • Preface
  • 1. Introduction
  • 1.1 What are strings?
  • 1.2 Why study string algorithms?
  • 1.3 What are our goals?
  • 1.4 A roadmap
  • 1.5 A Primer
  • 1.5.1 String notations and definitions
  • 1.5.2 Graph theory
  • 1.5.3 Running times
  • 1.5.4 Sets and combinatorics
  • 1.5.5 Numbers
  • 1.5.6 Data structures
  • 1.5.7 Probability
  • I. Exact Matching
  • 2. The Z Algorithm
  • 2.1 The exact matching problem
  • 2.2 Simple (slow) solution
  • 2.3 The Z algorithm
  • 2.4 Computing the Z values
  • 2.5 Summary and notes
  • 2.6 Exercises
  • 3. Boyer-Moore
  • 3.1 High-level description
  • 3.1.1 First rule: Next Matching Character
  • 3.1.2 Second rule: Good Shift Rule
  • 3.1.3 Complete algorithm
  • 3.2 Computing the Ri values for the next matching character rule
  • 3.3 Formalizing the Good Shift Rule
  • 3.4 Implementing the Good Shift Rule
  • 3.4.1 Computing the L(i) values
  • 3.4.2 Computing the l(i) values
  • 3.5 Summary and notes
  • 3.6 Exercises
  • 4. Knuth-Morris-Pratt
  • 4.1 KMP via deterministic finite automata
  • 4.1.1 The KMP DFA
  • 4.1.2 Using the memo array for string search
  • 4.1.3 Correctness and running time
  • 4.1.4 Computing memo
  • 4.2 KMP via the Z-values
  • 4.2.1 Running time of the spmi version of KMP
  • 4.2.2 Computing the spmi array
  • 4.3 Summary and notes
  • 4.4 Exercises
  • 5. Seminumerical String Matching
  • 5.1 Rabin-Karp fingerprinting
  • 5.1.1 Computing p
  • 5.1.2 Computing ts for every position s
  • 5.1.3 Time for addition, product, and comparison
  • 5.1.4 Quantifying and reducing false positives
  • 5.1.5 Reducing the error probability
  • 5.2 The Shift-And algorithm
  • 5.2.1 Space and runtime
  • 5.2.2 Extension to approximate matching
  • 5.3 Summary and notes
  • 5.4 Exercises
  • 6. Searching for Multiple Patterns
  • 6.1 Aho-Corasick-a prefix-based approach
  • 6.1.1 Search
  • 6.1.2 Handling patterns contained in other patterns
  • 6.1.3 Running time
  • 6.1.4 Computing f
  • 6.2 Wu-Manber-a suffix-based approach
  • 6.3 Summary and notes
  • 6.4 Exercises
  • II. Edit Distance
  • 7. Edit Distance for Inexact Matching
  • 7.1 Edit distance and alignments
  • 7.2 The string alignment problem
  • 7.2.1 Algorithm for minimum cost alignments
  • 7.2.2 Implementing the recursive algorithm
  • 7.3 Dynamic programming
  • 7.4 Finding the actual alignment: traceback
  • 7.5 Local and semi-global alignment
  • 7.5.1 Local alignment
  • 7.5.2 Semi-global alignment
  • 7.6 Summary and notes
  • 7.7 Exercises
  • 8. Edit Distance in Linear Space
  • 8.1 Using linear space to compute edit distance values
  • 8.2 Finding the actual alignment in linear space
  • 8.2.1 Hirschberg's algorithm
  • 8.2.2 Proof of running time
  • 8.3 Summary and notes
  • 8.4 Exercises
  • 9. Faster Edit Distance via the "Four Russians" Trick
  • 9.1 Dynamic programming blocks
  • 9.2 Precomputing f
  • 9.2.1 Offset encoding
  • 9.2.2 Number of possible inputs to f
  • 9.2.3 Storing f for quick access