UCSC 2nd year 1st semester data structures and algorithms
Algorithm | Preprocessing TIme | Matching Time |
---|---|---|
Naive | 0 | O((n - m + 1)m) |
Rabin-Karp | O(m) | O((n - m + 1)m) |
Finite Automation | O(m |โ|) | O(n) |
Knuth-Morris-Pratt | O(m) | O(n) |
n - Length of the Text, m(< n) - Length of the Pattern