Queries to find frequencies of a string within specified substrings | Python3 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
max_len = 100005 NEW_LINE cnt = [ 0 ] * max_len NEW_LINE def precompute ( s , K ) : NEW_LINE INDENT n = len ( s ) NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT cnt [ i + 1 ] = cnt [ i ] NEW_LINE if s [ i : len ( K ) + i ] == K : NEW_LINE INDENT cnt [ i + 1 ] += 1 NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " ABCABCABABC " NEW_LINE K = " ABC " NEW_LINE precompute ( s , K ) NEW_LINE Q = [ [ 1 , 6 ] , [ 5 , 11 ] ] NEW_LINE for it in Q : NEW_LINE INDENT print ( cnt [ it [ 1 ] - 1 ] - cnt [ it [ 0 ] - 1 ] ) NEW_LINE DEDENT DEDENT