Computer scienceAlgorithms and Data StructuresAlgorithmsString algorithmsSubstring search algorithms

Knuth-Morris-Pratt algorithm

The fewer shifts, the better

Report a typo

As you know from the theory, the KMP algorithm is more efficient than the naive approach in substring searching.

Given the pattern $s=ALO$ and the string $t=ALALALALALONG$ . Calculate the number of shifts made while using the KMP algorithm to search for the presence of $s$ in $t$ . Do not count as a shift the first step when the substring is positioned at the beginning of the string $t$ .

Note that the naive algorithm would perform

8

shifts until

s

is found, meanwhile KMP performs significantly fewer shifts. How many?

Enter a number

___

Create a free account to access the full topic