Computer scienceAlgorithms and data structuresAlgorithmsString algorithmsSubstring search algorithms

Knuth-Morris-Pratt algorithm

Time and memory complexities

Report a typo

What is the time and space complexity of the KMP algorithm for a pattern $s$ and a text $t$ ?

Select one option from the list

O(|s| + |t|), O(|t|)

O(|s| \cdot |t|), O(|s|)

O(|s|^2 + |t|), O(|s|)

O(|s| + |t|), O(|s|)

Create a free account to access the full topic