Prefix Function Π for KMP (Knuth Morris Pratt) Algorithm in Python

The prefix function Π for a pattern gives an idea about how the pattern matches against shifts of itself. This information can help in avoiding some useless shifts that are performed in the naive algorithm for string matching. It (Π[k]) is defined as the length of the largest proper prefix of pattern P that is also a proper suffix of P. It enables avoiding backtracking on the text string ‘T’. The algorithm to calculate Π can be found in textbooks or on several websites. Here is the python implementation of the algorithm mentioned in the algorithm book by CLRS. The string matching KMP algorithm is present here.

def calculate_PI(p):
	l = len(p)
	pi = [0]
	k = 0
	for i in xrange(1,l):
		while(k > 0 and p[k] != p[i]):
			k = pi[k-1]
		if (p[k] == p[i]):
			k = k+1
		pi.append(k)
	print "pattern is: ", p
	print "pi values are: ", pi

str = "civic"
calculate_PI(str)
str = "malyalam"
calculate_PI(str)
str = "ababababca"
calculate_PI(str)
str = "mississippi"
calculate_PI(str)

The output of the above code is as follows…

pattern is: civic
pi values are: [0, 0, 0, 0, 1]
pattern is: malyalam
pi values are: [0, 0, 0, 0, 0, 0, 0, 1]
pattern is: ababababca
pi values are: [0, 0, 1, 2, 3, 4, 5, 6, 0, 1]
pattern is: mississippi
pi values are: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]