Number of ways of choosing K equal substrings of any length for every query | C ++ implementation of the approach ; Function to generate all the sub - strings ; Length of the string ; Generate all sub - strings ; Count the occurrence of every sub - string ; Compute the Binomial Coefficient ; Calculate value of Binomial Coefficient in bottom up manner ; Base Cases ; Calculate value using previously stored values ; Function to return the result for a query ; Iterate for every unique sub - string ; Count the combinations ; Driver code ; Get all the sub - strings Store the occurrence of all the sub - strings ; Pre - computation ; Queries ; Perform queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define maxlen  100 NEW_LINE void generateSubStrings ( string s , unordered_map < string , int > & mpp ) { int l = s . length ( ) ; for ( int i = 0 ; i < l ; i ++ ) { string temp = " " ; for ( int j = i ; j < l ; j ++ ) { temp += s [ j ] ; mpp [ temp ] += 1 ; } } } void binomialCoeff ( int C [ maxlen ] [ maxlen ] ) { int i , j ; for ( i = 0 ; i < 100 ; i ++ ) { for ( j = 0 ; j < 100 ; j ++ ) { if ( j == 0 j == i ) C [ i ] [ j ] = 1 ; else C [ i ] [ j ] = C [ i - 1 ] [ j - 1 ] + C [ i - 1 ] [ j ] ; } } } int answerQuery ( unordered_map < string , int > & mpp , int C [ maxlen ] [ maxlen ] , int k ) { int ans = 0 ; for ( auto it : mpp ) { if ( it . second >= k ) ans += C [ it . second ] [ k ] ; } return ans ; } int main ( ) { string s = " aabaab " ; unordered_map < string , int > mpp ; generateSubStrings ( s , mpp ) ; int C [ maxlen ] [ maxlen ] ; memset ( C , 0 , sizeof C ) ; binomialCoeff ( C ) ; int queries [ ] = { 2 , 3 , 4 } ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; for ( int i = 0 ; i < q ; i ++ ) cout << answerQuery ( mpp , C , queries [ i ] ) << endl ; return 0 ; }