Computer scienceAlgorithms and Data StructuresAlgorithmsString algorithmsSubstring search algorithms

Prefix function

Understanding the prefix function in KMP

Report a typo

Hey there! This problem might be a bit unpredictable, but give it a go and let us know how you do!

The following code snippet shows a function that calculates the prefix function for a string. Identify the correct statements about this function and its relation to substring searching.

def prefix_function(pattern):
    prefix = [0]*len(pattern)
    j = 0
    for i in range(1,len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = prefix[j-1]
        if pattern[i] == pattern[j]:
            j += 1
        prefix[i] = j
    return prefix

Select one or more options from the list

This function follows the Knuth-Morris-Pratt (KMP) substring search algorithm.

The time complexity of this function is O(n), where n is the length of the pattern.

The prefix array indicates the occurrences of the substring in the text.

The pattern is the text we are searching in, not the substring we are searching for.

The function uses a pattern-dependent approach, and thus, the worst-case time complexity could be more than linear.

___

Create a free account to access the full topic