Count of substrings of a string containing another given string as a substring | Set 2 | C ++ program for the above approach ; Function to count the substrings of string containing another given string as a substring ; Store length of string S ; Store length of string T ; Store the required count of substrings ; Store the starting index of last occurence of T in S ; Iterate in range [ 0 , n1 - n2 ] ; Check if substring from i to i + n2 is equal to T ; Check if substring from i to i + n2 is equal to T ; Mark chk as false and break the loop ; If chk is true ; Add ( i + 1 - last ) * ( n1 - ( i + n2 - 1 ) ) to answer ; Update the last to i + 1 ; Print the answer ; Driver code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findOccurrences ( string S , string T ) { int n1 = S . size ( ) ; int n2 = T . size ( ) ; int ans = 0 ; int last = 0 ; for ( int i = 0 ; i <= n1 - n2 ; i ++ ) { bool chk = true ; for ( int j = 0 ; j < n2 ; j ++ ) { if ( T [ j ] != S [ i + j ] ) { chk = false ; break ; } } if ( chk ) { ans += ( i + 1 - last ) * ( n1 - ( i + n2 - 1 ) ) ; last = i + 1 ; } } cout << ans ; } int main ( ) { string S = " dabc " , T = " ab " ; findOccurrences ( S , T ) ; }