Page Index - Maksym-Botvin/study GitHub Wiki
7 page(s) in this GitHub Wiki:
- Home
- Knuth–Morris–Pratt algorithm
- Components of KMP Algorithm:
- 1. The Prefix Function (Π): The Prefix Function, Π for a pattern encapsulates knowledge about how the pattern matches against the shift of itself. This information can be used to avoid a useless shift of the pattern 'p.' In other words, this enables avoiding backtracking of the string 'S.'
- 2. The KMP Matcher: With string 'S,' pattern 'p' and prefix function 'Π' as inputs, find the occurrence of 'p' in 'S' and returns the number of shifts of 'p' after which occurrences are found.
- The Prefix Function (Π)
- Knuth–Morris–Pratt algorithm