O(nxm) describes work proportional to text length n multiplied by pattern length m. Character-by-character matching can reach this cost when it checks many pattern characters at each text position. section 4.0
String-matching algorithms can encounter this cost in different ways:
- Brute-force matching may compare many characters before finding a mismatch. section 4.0
- Rabin–Karp can degrade to O(nxm) when frequent hash collisions force character-by-character verification. section 4.4
- Horspool can fall back to O(nxm) on tiny-alphabet or repetitive inputs when shifts stay short. section 6.4
A hash collision
A simple addition-based hash gives “ACT” and “CAT” the same value. Repeated collisions can force Rabin–Karp to verify characters and lose its average linear-time performance. section 4.4
Table 4.1 Comparison table of various string matching algorithms
|
Algorithm
|
Advantages
|
Disadvantages
|
Use cases
|
|
Rabin Karp
|
Converts strings to fast numeric hashes, allowing O(1) window sliding.
|
Degrades to catastrophic O(n x m) if weak hashes resulting in constant collisions
|
Plagiarism detection and bioinformatics
|
|
Knuth-Morris-Pratt
|
Guarantees deterministic O(n) time by creating Longest Prefix Suffix array
|
Wastes O(m) memory and provides zero speed advantage if the pattern lacks internal repetition.
|
Real time data streaming and log analysis
|
|
Boyer Moore
|
Achieves sub-linear performance by scanning right-to-left and skipping massive chunks of mismatched text.
|
Highly complex to implement the "Bad Character" tables, and degrades on highly repetitive text.
|
Text Editors and Integrated Development Environment (IDE)
|
|
Aho-Corasick
|
Constructs a state-machine to search for thousands of different patterns simultaneously in a single O(n) pass
|
Imposes massive memory overhead to build and store the deterministic finite states
|
Mass virus scanning against massive signature databases
|
Compare how Rabin–Karp, KMP, Boyer–Moore, and Aho–Corasick trade performance against other costs and limitations. section 4.0
