Queries to find frequencies of a string within specified substrings | Java program to find frequency of a string K in a substring [ L , R ] in S ; Store the frequency of string for each index ; Compute and store frequencies for every index ; Driver code
class GFG { static int max_len = 100005 ; static int cnt [ ] = new int [ max_len ] ; public static void precompute ( String s , String K ) { int n = s . length ( ) ; for ( int i = 0 ; i < n - 2 ; i ++ ) { cnt [ i + 1 ] = cnt [ i ] ; if ( s . substring ( i , i + K . length ( ) ) . equals ( K ) ) { cnt [ i + 1 ] += 1 ; } } cnt [ n - 2 + 1 ] = cnt [ n - 2 ] ; } public static void main ( String [ ] args ) { String s = " ABCABCABABC " ; String K = " ABC " ; precompute ( s , K ) ; int Q [ ] [ ] = { { 1 , 6 } , { 5 , 11 } } ; for ( int it = 0 ; it < Q . length ; it ++ ) { System . out . println ( cnt [ Q [ it ] [ 1 ] - 1 ] - cnt [ Q [ it ] [ 0 ] - 1 ] ) ; } } }