String Algorithms

Specialized algorithms for processing, searching, and analyzing text and sequences. These techniques underpin search engines, DNA sequencing, text editors, and data compression—any application where finding patterns in sequences matters.

Intermediate to Advanced

• Basic pattern matching: Intermediate
• Suffix trees and arrays: Advanced
• Advanced applications (BWT, FM-index): Advanced

The invisible infrastructure of text: Every time you use Ctrl+F, run grep, or search Google, you’re using string algorithms. But their reach extends far beyond text processing:

• Computational biology: DNA sequence alignment uses string matching at scale (3 billion base pairs in human genome)
• Plagiarism detection: Finding similar documents requires efficient approximate string matching
• Data compression: Burrows-Wheeler Transform powers bzip2 and is used in genome compression
• Version control: Git’s diff algorithm uses longest common subsequence

War Story - The Suffix Tree Revolution: In 1997, researchers needed to search massive DNA databases quickly. Naive search would take hours. Suffix trees reduced search time from O(nm) to O(m) where m is the query length—making genome-scale search practical. This single data structure enabled the genomics revolution. Today, tools like BLAST use suffix tree variants to search billions of DNA sequences in seconds.

1. Naive String Matching - Baseline O(nm) pattern matching
2. KMP (Knuth-Morris-Pratt) - O(n+m) pattern matching using failure function
3. Boyer-Moore - Practical fast string search with skip heuristics
4. Rabin-Karp - Rolling hash for multiple pattern search
5. Suffix Arrays - Space-efficient alternative to suffix trees
6. Longest Common Subsequence (LCS) - Dynamic programming on strings

7. Suffix Trees - O(n) construction (Ukkonen’s algorithm), O(m) pattern search
8. Aho-Corasick - Multi-pattern matching automaton
9. Burrows-Wheeler Transform (BWT) - Reversible text transformation for compression
10. FM-Index - Compressed full-text index combining BWT and suffix arrays
11. Edit Distance - Levenshtein distance, alignment algorithms
12. Z-Algorithm - Linear-time pattern matching preprocessing

• Required:

  • Basic algorithms and data structures
  • Dynamic programming
  • Understanding of hash functions
  • Basic automata theory helpful

• Helpful:

  • Tries and prefix trees
  • Basic probability for randomized algorithms (Rabin-Karp)
  • Familiarity with compression concepts

Setup: You’re building a search feature for a text editor with 1GB of text. Users type queries and expect instant results. How do you handle this?

Naive approach: For each search, scan the entire text comparing at each position. This is O(nm) per query—way too slow for interactive search.

First insight: Can we preprocess the text once, then answer queries quickly?

Key question: What if we could build an index of where every substring appears? This leads naturally to suffix trees—store all suffixes in a trie-like structure.

The revelation: Suffix trees allow O(m) search regardless of text size. The preprocessing cost is amortized over thousands of searches.

Generalization: The pattern of “expensive preprocessing, fast queries” recurs throughout computer science. Understanding this tradeoff is crucial.

Setup: You have two DNA sequences with millions of base pairs. They’re related but have mutations—some letters changed, inserted, or deleted. How similar are they?

Naive: Try to align them by brute force. Exponentially many possibilities.

Insight: This is edit distance! Use dynamic programming—if we know the best alignment of shorter prefixes, we can extend it.

The algorithm: Build table where entry (i,j) is the minimum edits to transform first i characters of string 1 into first j characters of string 2.

Recurrence:

• If characters match: dp[i][j] = dp[i-1][j-1]
• Otherwise: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (representing deletion, insertion, or substitution)

The impact: This algorithm (Needleman-Wunsch for biology) enabled the Human Genome Project. Understanding evolutionary relationships requires comparing DNA sequences.

Setup: You need to compress a large text file. Simple schemes like Huffman coding work character-by-character. Can you exploit longer patterns?

Key observation: Text has repeated substrings. If we could group similar contexts together, they’d compress better.

Enter BWT: Rearrange characters so that similar contexts are adjacent. Magically, this transformation is reversible!

Why it works: BWT creates long runs of repeated characters, which compress extremely well with run-length encoding.

Real-world impact: bzip2 uses BWT. Modern DNA compression achieves 1000x compression ratios by exploiting that genomes within a species are 99%+ similar.

Pattern recognition everywhere: String algorithms formalize pattern matching—a fundamental cognitive task:

• Spell checking: Edit distance determines if “recieve” is close to “receive”
• Autocomplete: Tries enable fast prefix matching for suggestions
• Plagiarism detection: Finding similar passages uses approximate string matching
• Code analysis: Finding duplicated code uses longest common subsequence

The algorithms teach us to think about similarity, patterns, and efficient indexing—skills transferable to any domain involving sequential data.

The insight: When a mismatch occurs, use information from the partial match to skip ahead intelligently rather than backing up to the start.

Failure function: Preprocess pattern to find longest proper prefix that’s also a suffix at each position.

Complexity: O(n+m) time, O(m) space When to use: When you need guaranteed linear time, or pattern is reused many times

The structure: Compressed trie of all suffixes. Each edge labeled with substring, leaves represent suffix positions.

Construction: Ukkonen’s algorithm builds in O(n) time using clever online construction with suffix links.

Applications:

• Pattern matching in O(m) time
• Finding longest repeated substring
• Finding longest common substring of multiple strings
• Generalized suffix trees for multiple texts

Space cost: O(n) nodes but large constants—practical implementations use suffix arrays

The insight: We don’t need the full tree structure—just the sorted order of suffixes.

Construction: Can be built in O(n) time with careful algorithms (though O(n log n) sorting is simpler and often sufficient)

Space: Just an array of integers—much more practical than suffix trees

Search: O(m log n) with binary search, or O(m + log n) with LCP (longest common prefix) array

The transformation:

1. Generate all rotations of the text
2. Sort them lexicographically
3. Take the last column

Example:

• Text: “banana”
• Rotations sorted: “abanan”, “anaban”, “banana”, “nanaba”, “nabana”, “naaban”
• BWT: “nnbaaa” (last column)

Magic: This is reversible! Can reconstruct original from BWT.

Why it helps compression: Similar contexts end up adjacent, creating runs of repeated characters.

• Gusfield: “Algorithms on Strings, Trees, and Sequences” - The definitive reference for string algorithms, especially strong on biological applications
• Crochemore et al: “Algorithms on Strings” - Comprehensive, more mathematical treatment
• Skiena §18 - Practical string matching with war stories
• Sedgewick & Wayne §5.3-5.4 - Accessible introduction with Java implementations

• Stanford CS166 lecture notes (Keith Schwarz) - Excellent suffix tree coverage
• Competitive programming resources (Codeforces, TopCoder) - Many practical problems

• Ukkonen (1995): “On-line construction of suffix trees” - The breakthrough O(n) algorithm
• Ferragina & Manzini (2000): “Opportunistic data structures with applications” - FM-Index paper
• Burrows & Wheeler (1994): “A block-sorting lossless data compression algorithm”

• Dynamic Programming: Edit distance and sequence alignment are classic DP problems
• Data Structures: Tries, suffix trees, and automata are sophisticated tree structures
• Computational Biology: DNA/protein sequence analysis is dominated by string algorithms
• Compression: BWT, LZ77/78 algorithms, and Huffman coding combine for practical compression
• Automata Theory: Pattern matching automata (Aho-Corasick) connect to formal languages
• Hashing: Rabin-Karp uses rolling hashes; hashing is crucial for many modern variants

1. Search Engine from Scratch

   • Implement suffix array construction
   • Build search interface with highlighting
   • Compare performance: naive vs. KMP vs. suffix array
   • Add fuzzy search with edit distance

2. DNA Sequence Aligner

   • Implement Smith-Waterman local alignment
   • Visualize alignment with gaps and mismatches
   • Compare runtime on sequences of varying lengths
   • Explore heuristics used by BLAST

3. Text Compression Tool

   • Implement Burrows-Wheeler Transform
   • Add move-to-front encoding and run-length encoding
   • Compare compression ratios with existing tools
   • Visualize how BWT groups similar contexts

4. Plagiarism Detector

   • Use n-gram fingerprinting with rolling hashes
   • Implement shingling for document similarity
   • Build system to find similar passages across documents
   • Explore threshold tuning for precision/recall

5. Pattern Matching Visualization

   • Visualize KMP failure function construction
   • Animate suffix tree construction (Ukkonen’s algorithm)
   • Compare search patterns across different algorithms
   • Interactive tool for understanding string algorithm behavior

2-4 lectures depending on depth

• 1 lecture: Basic pattern matching (naive, KMP, Boyer-Moore), introduction to suffix structures
• 2 lectures: + Edit distance, LCS, suffix arrays with construction
• 3 lectures: + Suffix trees, Aho-Corasick multi-pattern matching
• 4 lectures: + BWT, FM-index, advanced applications in compression and bioinformatics

1. “String matching is a solved problem”

   • False! New variants constantly emerge: approximate matching, compressed search, streaming text. Active research continues.

2. “Suffix trees are always better than suffix arrays”

   • False! Suffix arrays use much less space. With LCP array, they support nearly all suffix tree operations. Practical implementations often prefer suffix arrays.

3. “KMP is faster than naive search”

   • Not always! For short patterns or small alphabets, naive search’s simplicity and cache-friendliness can win. Boyer-Moore often beats both in practice.

4. “Edit distance only works for strings”

   • False! The DP algorithm generalizes to any sequence comparison: time series, protein structures, program traces. The key is defining meaningful insertion/deletion/substitution costs.

5. “BWT is just for compression”

   • False! BWT is fundamental to FM-index, which enables compressed full-text search. It’s used in bioinformatics tools that search terabytes of genomic data.

Search and indexing:

• Full-text search engines (Lucene uses suffix-based techniques)
• Code search in IDEs
• Genome databases (NCBI BLAST uses suffix tree variants)

Bioinformatics:

• Sequence alignment (BLAST, Bowtie, BWA)
• Genome assembly
• RNA structure prediction
• Phylogenetic analysis

Data compression:

• bzip2 (BWT + Huffman)
• Modern DNA compression (exploits sequence similarity)
• Log file compression

Security:

• Intrusion detection (pattern matching in network traffic)
• Plagiarism and duplicate detection
• Malware signature matching

Version control:

• diff algorithms (LCS-based)
• Binary diff tools

Traditional (banking model):

“Here’s KMP. It uses a failure function. Here’s the algorithm. Memorize the failure function construction.”

Problem-posing approach:

“You’re searching a huge text file. Naive search backtracks constantly—can we avoid that? When we have a partial match that fails, what information do we have? Could we use it to skip ahead? Let’s discover what that ‘skip ahead’ rule should be…”

The difference: Students understand WHY we need clever techniques (scale demands efficiency) and discover the key insights themselves (reusing partial match information) rather than memorizing algorithms.

Curriculum placement:

• Week 4-6 for graduate courses (after dynamic programming)
• Can be covered early (basic matching) with advanced topics later (suffix structures)

Prerequisites check: Students need solid DP background for edit distance and sequence alignment. Suffix structures require comfort with tree data structures and recursion.

Why this timing: String algorithms are self-contained but build on DP. They provide concrete, relatable applications of abstract techniques.

The data explosion: Modern applications process unprecedented text volumes:

• Social media: billions of posts daily requiring search and analysis
• Genomics: thousands of genomes sequenced, requiring comparative analysis
• Log analysis: terabytes of logs requiring pattern matching
• Code search: billions of lines of code in repositories

Classic algorithms still dominate: Despite decades of research, KMP, suffix arrays, and BWT remain fundamental. Understanding these “old” algorithms is essential—they’re not being replaced, they’re being adapted for new contexts (distributed systems, compressed search, streaming data).

Cross-disciplinary impact: String algorithms aren’t just for CS—they’re essential tools in biology, linguistics, cybersecurity, and data science. Learning them opens doors to interdisciplinary research.

Ready for students? ✓ Yes - motivated by real applications, connects theory to practice, provides multiple entry points from basic to advanced.