Computer scienceAlgorithms and Data StructuresAlgorithmsString algorithmsSubstring search algorithms

Knuth-Morris-Pratt algorithm

Statements

Report a typo

Which of the statements below about the KMP algorithm is correct?

Select one option from the list

The algorithm calculates the prefix function for both a pattern and a text first, then compares them to find the pattern in the text.

The algorithm compares a pattern with substrings of a text trying to find a complete matching. To decrease the number of comparisons, it uses the prefix function for finding an optimal pattern shift.

The algorithm compares a pattern with substring of a text trying to find a complete matching. In case of a mismatch, the algorithm shifts the pattern by one symbol and starts a new iteration.

The algorithm calculates the prefix function for a text first, then uses this prefix function to find a pattern in the text.

___

Create a free account to access the full topic