tag

#pattern-matching

26 pages tagged

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.23 Complexity Analysis

16.23 Complexity Analysis Problem String algorithms often look deceptively simple. A few nested loops may be harmless for short text but catastrophic for large input. A suffix-array comparison may appear to take O(log n) binary-search steps, while each comparison secretly scans many characters. A hash-based algorithm may appear constant time, but only after preprocessing and with collision assumptions. The challenge is to analyze string algorithms honestly, including hidden costs such...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.1 Exact Matching

16.1 Exact Matching Problem Given a text string and a pattern string, determine whether the pattern occurs in the text and, if so, find all positions where the match begins. This is one of the oldest and most fundamental problems in computer science. Search engines look for query terms inside documents. Compilers search for keywords inside source code. Text editors perform find-and-replace operations. DNA analysis systems search for gene sequences...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.25 Real-World String Processing Patterns

16.25 Real-World String Processing Patterns Problem After learning dozens of string algorithms, a natural question remains: What do real systems actually do? Textbooks often present algorithms in isolation: KMP solves pattern matching. Tries solve prefix search. Suffix arrays solve substring search. Edit distance solves similarity. Production systems rarely look like this. Instead, they combine multiple techniques into processing pipelines. The challenge is to recognize recurring architectural patterns that appear across...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.18 Unicode and Normalization

16.18 Unicode and Normalization Problem Many string algorithms assume that a string is simply a sequence of characters. For English text, this assumption often appears correct. hello world algorithm A character seems to correspond to: One symbol One storage unit One display position Unicode breaks this assumption. Consider: é This character may be represented as: U+00E9 or as: U+0065 U+0301 which means: e + combining acute accent Visually they appear...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.12 Manacher Algorithm

16.12 Manacher Algorithm Problem You need to find palindromic substrings efficiently. Given: forgeeksskeegfor the longest palindromic substring is: geeksskeeg A brute-force solution checks every substring and tests whether it is a palindrome. There are O(n²) substrings, and each check may cost O(n) , giving O(n³) time if implemented directly. Even a better expand-around-center approach still costs O(n²) in the worst case. The challenge is to find all palindrome radii, and...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.2 Knuth-Morris-Pratt (KMP)

16.2 Knuth-Morris-Pratt (KMP) Problem The naive exact matching algorithm repeatedly compares the same characters after every mismatch. When the text and pattern contain repeated prefixes, large amounts of work are duplicated. Consider: Text: AAAAAAAAAAAAAAAA Pattern: AAAAAB The naive algorithm repeatedly verifies the same sequence of A characters before discovering that the final character differs. The challenge is to reuse information gained from previous comparisons instead of restarting from the beginning...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.9 Longest Common Prefix (LCP) Arrays

16.9 Longest Common Prefix (LCP) Arrays Problem In the previous recipe, you built a suffix array and used it to perform efficient substring searches. Consider the suffix array for: banana Rank Position Suffix 0 5 a 1 3 ana 2 1 anana 3 0 banana 4 4 na 5 2 nana Suppose you want to answer questions such as: What is the longest repeated substring? How many distinct substrings exist?...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.14 Longest Common Substring

16.14 Longest Common Substring Problem Given two strings, find the longest contiguous block of characters that appears in both. For example: A = banana B = ananas The longest common substring is: anana This differs from the longest common subsequence. A substring must be contiguous. A subsequence may skip characters. substring: consecutive characters subsequence: characters in order, with gaps allowed The challenge is to find the longest shared contiguous region...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.8 Suffix Arrays

16.8 Suffix Arrays Problem Suppose you need to answer many substring queries against the same text. For one query, a linear scan is acceptable: Text: bananabandana Pattern: ana But if the text is large and the number of queries is high, scanning from the beginning each time is wasteful. You want a structure that preprocesses the text once and then answers substring queries quickly. Solution A suffix array stores all...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.22 Building a Search Engine

16.22 Building a Search Engine Problem Throughout this chapter, we studied individual string-processing techniques: Tokenization Tries Hashing Aho-Corasick Suffix Arrays Edit Distance Text Indexes Real systems rarely use these algorithms in isolation. Consider a search engine. Users expect: Fast queries Typo tolerance Phrase search Prefix completion Relevant ranking Large-scale indexing No single algorithm provides all of these capabilities. The challenge is to combine multiple string-processing techniques into a practical search...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.3 Z Algorithm

16.3 Z Algorithm Problem Many string algorithms need to answer the question: How many characters match between a string prefix and a substring starting at a particular position? Consider: ABABABCA At position 2: ABABABCA ABABCA The substring beginning at position 2 shares four characters with the prefix: ABAB A naive solution compares characters one by one for every position. For a string of length n , this may require: O(n²)...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.7 Aho-Corasick

16.7 Aho-Corasick Problem Suppose you need to search a text for thousands of patterns simultaneously. Consider a dictionary: he her hers hero help hello world search engine algorithm and a text stream: the hero helped her while the search engine processed the world A straightforward solution runs a separate search for every pattern. search("he") search("her") search("hers") search("hero") ... Even if each search uses KMP or Boyer-Moore, the text must be...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.6 Trie Matching

16.6 Trie Matching Problem Suppose you need to search for many patterns simultaneously. Consider a dictionary: he her hers hero help hello and a text: hello hero and her helpers A straightforward approach searches for each word independently. search("he") search("her") search("hers") search("hero") search("help") search("hello") If there are thousands of patterns, the same text characters may be scanned repeatedly. The cost grows with both the text length and the number of...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.15 Lexicographic Order

16.15 Lexicographic Order Problem Many string algorithms depend on a precise ordering of strings. Suffix arrays sort suffixes. Dictionaries sort words. Search systems compare terms. Databases compare keys. Compression algorithms order repeated fragments. In all of these cases, the algorithm must answer a basic question: Which string comes first? For example: apple < banana app < apple cat < catalog The challenge is to define this ordering exactly and implement...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.24 Testing String Algorithms

16.24 Testing String Algorithms Problem String algorithms are easy to implement incorrectly. Most failures are small: Off-by-one error Wrong boundary condition Incorrect empty-pattern behavior Unicode mismatch Duplicate match omission Failure to report overlapping matches These bugs often pass simple tests. For example, a matcher may work for: Text: hello world Pattern: world but fail for: Text: aaaaa Pattern: aaa because overlapping matches are mishandled. The challenge is to test string...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.5 Boyer-Moore Overview

16.5 Boyer-Moore Overview Problem Most exact matching algorithms process the text from left to right. Consider: Text: HERE IS A SIMPLE EXAMPLE Pattern: EXAMPLE A typical algorithm begins by comparing: E E then: X X and continues forward. This approach works well, but it often examines many characters that ultimately contribute nothing to the search. Human readers rarely search this way. When looking for a word in a sentence, we...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.10 Suffix Automata

16.10 Suffix Automata Problem Suppose you need to answer questions such as: Does a substring occur in the text? How many distinct substrings exist? What is the longest repeated substring? How many times does a substring appear? What is the longest common substring between two strings? A suffix array and LCP array can answer many of these questions efficiently, but they are fundamentally indexing structures. Queries often require binary searches,...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.13 Edit Distance

16.13 Edit Distance Problem Exact matching assumes that strings must be identical. Consider: kitten sitting An exact matcher reports failure immediately because the strings differ. In many applications, however, similarity matters more than equality. Examples include: Spell checking Search suggestions OCR correction DNA sequence alignment Plagiarism detection Data deduplication Natural language processing The challenge is to measure how different two strings are and to do so efficiently. Solution Edit distance...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.20 Choosing the Right String Algorithm

16.20 Choosing the Right String Algorithm Problem This chapter introduced a large collection of string-processing techniques: Naive matching KMP Z Algorithm Rabin-Karp Boyer-Moore Tries Aho-Corasick Suffix Arrays LCP Arrays Suffix Automata Eertrees Manacher's Algorithm Edit Distance String Hashing A common question arises: Which algorithm should I use? Many algorithms solve related problems, but their strengths differ significantly. Choosing the wrong algorithm can increase complexity, memory usage, implementation effort, or runtime....
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.11 Palindromic Trees (Eertrees)

16.11 Palindromic Trees (Eertrees) Problem Many string algorithms focus on prefixes, suffixes, or arbitrary substrings. Palindromes introduce a different type of structure. A palindrome reads the same forward and backward. Examples: a aa aba abba racecar Given a string, you may want to answer questions such as: What palindromes occur in the text? How many distinct palindromes exist? How often does each palindrome appear? What is the longest palindromic substring?...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.16 String Hashing

16.16 String Hashing Problem Many string algorithms repeatedly compare substrings. Consider: Text = abracadabra Suppose you want to determine whether: abra appears multiple times. A direct comparison examines characters one by one. abra abra This is inexpensive for a single query. Now imagine: Millions of substring comparisons Large documents Plagiarism detection Search indexing DNA analysis Duplicate detection Repeated character-by-character comparison becomes a bottleneck. The challenge is to compare substrings quickly...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook ›

Chapter 16. String Algorithms

Chapter 16. String Algorithms
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.4 Rabin-Karp

16.4 Rabin-Karp Problem Suppose you need to search for a pattern inside a large text. Text: THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG Pattern: BROWN A straightforward algorithm compares characters one by one. Even efficient algorithms such as KMP and the Z Algorithm ultimately rely on direct character comparisons. Now consider a different situation: Text length = 10,000,000 Patterns = thousands Searches/day = millions Repeated character-by-character comparison becomes expensive. The challenge is to compare substrings quickly...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.19 Token Streams

16.19 Token Streams Problem Most string algorithms operate on characters. Many real systems operate on tokens. A compiler does not usually search raw source code character by character. It first groups characters into tokens: if identifier = number { } A search engine does not usually index raw characters. It tokenizes documents into words, terms, phrases, or normalized units. The challenge is to apply string-algorithm ideas to sequences whose elements...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.21 Text Indexing

16.21 Text Indexing Problem A single pattern search scans one text once. A text index solves a different problem: one or more large texts are stored, and many queries arrive later. Examples: Find all documents containing "algorithm" Find every occurrence of "banana" Find phrases beginning with "dynamic programming" Find logs containing both "timeout" and "database" Scanning every document for every query is too slow. The challenge is to preprocess text...
algorithms strings pattern-matching Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.17 Compressed Strings

16.17 Compressed Strings Problem Many strings contain repeated structure. Examples: aaaaaa abababab the the the the A direct representation stores every character explicitly. That is simple, but it can waste space and make repeated operations expensive. Suppose a string is represented as: a repeated 1,000,000 times It is inefficient to store and scan one million characters when the structure can be described compactly. The challenge is to represent repetitive strings...
algorithms strings pattern-matching Jun 1, 2026