Count of occurrences of each prefix in a string using modified KMP algorithm | Java program for the above approach ; 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 ; Driver Code ; Given String ; Function Call
import java . util . * ; class GFG { static void print ( int [ ] occ , String s ) { for ( int i = 1 ; i <= s . length ( ) - 1 ; i ++ ) { System . out . print ( s . substring ( 0 , i ) + " ▁ occurs ▁ " + occ [ i ] + " ▁ times . " + "NEW_LINE"); } } static int [ ] prefix_function ( String s ) { int [ ] LPS = new int [ s . length ( ) ] ; LPS [ 0 ] = 0 ; for ( int i = 1 ; i < s . length ( ) ; i ++ ) { int j = LPS [ i - 1 ] ; while ( j > 0 && s . charAt ( i ) != s . charAt ( j ) ) { j = LPS [ j - 1 ] ; } if ( s . charAt ( i ) == s . charAt ( j ) ) { LPS [ i ] = j + 1 ; } else { LPS [ i ] = 0 ; } } return LPS ; } static void count_occurence ( String s ) { int n = s . length ( ) ; int [ ] LPS = prefix_function ( s ) ; int [ ] occ = new int [ n + 1 ] ; for ( int i = 0 ; i < n ; i ++ ) { occ [ LPS [ i ] ] ++ ; } for ( int i = n - 1 ; i > 0 ; i -- ) { occ [ LPS [ i - 1 ] ] += occ [ i ] ; } for ( int i = 0 ; i <= n ; i ++ ) occ [ i ] ++ ; print ( occ , s ) ; } public static void main ( String [ ] args ) { String A = " ABACABA " ; count_occurence ( A ) ; } }