Computer scienceAlgorithms and Data StructuresAlgorithmsString algorithmsSubstring search algorithms

Rabin-Karp algorithm

Time complexity

Report a typo

Assume that $occ$ is the number of times a pattern $p$ occurs in a text $t$ . What is the running time of the Rabin-Karp algorithm in this case?

Select one or more options from the list

O(|t| + |p| + occ)

O(|p| + occ)

O(|t| + occ \cdot |p|)

O(|p| + occ \cdot |t|)

___

Create a free account to access the full topic