After j letters match and the next one does not, those j text letters are already known: they equal the pattern’s first j. KMP precomputes, for each prefix of the pattern, how much of it can still be matched after a slide (its longest border), so it never moves backwards in the text.
- Average time
- O(n + m)
- Space
- O(m)