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
def Print ( occ , s ) : NEW_LINE INDENT for i in range ( 1 , len ( s ) + 1 ) : NEW_LINE INDENT print ( s [ 0 : i ] , " occur " , occ [ i ] , " times . " ) NEW_LINE DEDENT DEDENT def prefix_function ( s ) : NEW_LINE INDENT LPS = [ 0 for i in range ( len ( s ) ) ] NEW_LINE for i in range ( 1 , len ( s ) ) : NEW_LINE INDENT j = LPS [ i - 1 ] NEW_LINE while ( j > 0 and s [ i ] != s [ j ] ) : NEW_LINE INDENT j = LPS [ j - 1 ] NEW_LINE DEDENT if ( s [ i ] == s [ j ] ) : NEW_LINE INDENT LPS [ i ] = j + 1 NEW_LINE DEDENT else : NEW_LINE INDENT LPS [ i ] = 0 NEW_LINE DEDENT DEDENT return LPS NEW_LINE DEDENT def count_occurence ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE LPS = prefix_function ( s ) NEW_LINE occ = [ 0 for i in range ( n + 1 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT occ [ LPS [ i ] ] += 1 NEW_LINE DEDENT for i in range ( n - 1 , 0 , - 1 ) : NEW_LINE INDENT occ [ LPS [ i - 1 ] ] += occ [ i ] NEW_LINE DEDENT for i in range ( n + 1 ) : NEW_LINE INDENT occ [ i ] += 1 NEW_LINE DEDENT Print ( occ , s ) NEW_LINE DEDENT A = " ABACABA " NEW_LINE count_occurence ( A ) NEW_LINE