String Matching Algorithms
Here is a cleaner assignment-style version with an image included.
String matching algorithms are used to find whether a pattern appears inside a text. The
three common methods are Naive String Matching, Rabin-Karp, and Knuth-Morris-Pratt
(KMP). Each has different performance and use cases.
1. Naive String Matching
The Naive algorithm compares the pattern with the text at every possible position, one
character at a time. It is simple to understand and implement, but it can become slow
for large inputs.
2. Rabin-Karp
Rabin-Karp uses hashing to compare the pattern with text substrings. It is efficient on
average and especially useful when searching for multiple patterns, but hash collisions
can reduce its performance.
3. Knuth-Morris-Pratt
KMP improves search efficiency by preprocessing the pattern and using a prefix table to
avoid repeating comparisons. It provides consistent linear-time performance and is very
effective for large texts.
Time Complexity
Algorithm Best Case Average Case Worst Case
Naive String Matching 𝑂(𝑛) 𝑂(𝑛𝑚) 𝑂(𝑛𝑚)
Rabin-Karp 𝑂(𝑛 + 𝑚) 𝑂(𝑛 + 𝑚) 𝑂(𝑛𝑚)
KMP 𝑂(𝑛 + 𝑚) 𝑂(𝑛 + 𝑚) 𝑂(𝑛 + 𝑚)
Here, 𝑛is the text length and 𝑚is the pattern length.
Strengths and Weaknesses
• Naive String Matching: easy to code, but inefficient for large texts and patterns.
• Rabin-Karp: good for multiple pattern search, but depends on good hashing.
• KMP: fastest and most reliable in worst-case scenarios, but more complex to
understand.
Comparison
• For small text and short patterns, Naive matching is often acceptable.
• For multiple searches or hash-based optimization, Rabin-Karp is useful.
• For large text and guaranteed efficiency, KMP is the best choice.