An algorithm that locates a pattern within a string.
- Variations include finding the first occurence and all occurences.
- n = len(text)
- m = len(pattern)
- Algorithms
- Brute Force Pattern Matching
- Intuitive and simple
- Not efficient
- Boyer-Moore
- Preprocesses the pattern
- Knuth-Morris-Pratt
- Preprocesses the pattern
- Rabin-Karp
- Reduces the problem to integer matching, going for a LSD Radix Sort kind of approach
- Brute Force Pattern Matching
| Best Case | Worst Case | ||
|---|---|---|---|
| Brute Force | No occurrences | ||
| Single occurence | |||
| All Occurencess | |||
| Boyer-Moore | No occurrences | ||
| Single occurence | |||
| All Occurencess | |||
| KMP | No occurrences | ||
| Single occurence | |||
| All Occurencess | |||
| Rabin-Karp | No occurrences | ||
| Single occurence | |||
| All Occurencess |