human
Count of occurrences of each prefix in a string using modified KMP algorithm | Function to print the count of all prefix in the given string.
Iterate over string s.
Print the prefix and their frequency.
Function to implement the LPS array to store the longest prefix which is also a suffix for every substring of the string S.
Array to store LPS values Value of lps [ 0 ] is 0 by definition.
Find the values of LPS [ i ] for the rest of the string using two pointers and DP.
Initially set the value of j as the longest prefix that is also a suffix for i as LPS [ i - 1 ].
Check if the suffix of length j + 1 is also a prefix.
If s [ i ] = s [ j ] then , assign LPS [ i ] as j + 1.
If we reached j = 0 , assign LPS [ i ] as 0 as there was no prefix equal to suffix.
Return the calculated LPS array.
Function to count the occurrence of all the prefix in the string S.
Call the prefix_function to get LPS.
To store the occurrence of all the prefix.
Count all the suffixes that are also prefix.
Add the occurences of i to smaller prefixes.
Adding 1 to all occ [ i ] for all the orignal prefix.
Function Call to print the occurence of all the prefix.
Given String.
Function Call"
How can the above be solved in Python?
assistant
#Here is code to count of occurrences of each prefix in a string using modified KMP algorithm and the other steps required.
 def Print ( occ , s ) :
	for i in range ( 1 , len ( s ) + 1 ) :
		print ( s [ 0 : i ] , " occur " , occ [ i ] , " times . " )
def prefix_function ( s ) :
	LPS = [ 0 for i in range ( len ( s ) ) ]
	for i in range ( 1 , len ( s ) ) :
		j = LPS [ i - 1 ]
		while ( j > 0 and s [ i ] != s [ j ] ) :
			j = LPS [ j - 1 ]
		if ( s [ i ] == s [ j ] ) :
			LPS [ i ] = j + 1
		else :
			LPS [ i ] = 0
	return LPS
def count_occurence ( s ) :
	n = len ( s )
	LPS = prefix_function ( s )
	occ = [ 0 for i in range ( n + 1 ) ]
	for i in range ( n ) :
		occ [ LPS [ i ] ] += 1
	for i in range ( n - 1 , 0 , - 1 ) :
		occ [ LPS [ i - 1 ] ] += occ [ i ]
	for i in range ( n + 1 ) :
		occ [ i ] += 1
	Print ( occ , s )
A = " ABACABA "
count_occurence ( A )