Queries to find frequencies of a string within specified substrings | C ++ 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
#include <bits/stdc++.h> NEW_LINE #define max_len  100005 NEW_LINE using namespace std ; int cnt [ max_len ] ; void precompute ( string s , string K ) { int n = s . size ( ) ; for ( int i = 0 ; i < n - 1 ; i ++ ) { cnt [ i + 1 ] = cnt [ i ] + ( s . substr ( i , K . size ( ) ) == K ) ; } } int main ( ) { string s = " ABCABCABABC " ; string K = " ABC " ; precompute ( s , K ) ; vector < pair < int , int > > Q = { { 1 , 6 } , { 5 , 11 } } ; for ( auto it : Q ) { cout << cnt [ it . second - 1 ] - cnt [ it . first - 1 ] << endl ; } return 0 ; }