Different substrings in a string that start and end with given strings | Cpp program to find number of different sub strings ; function to return number of different sub - strings ; initially our answer is zero . ; find the length of given strings ; currently make array and initially put zero . ; find occurrence of " a " and " b " in string " s " ; We use a hash to make sure that same substring is not counted twice . ; go through all the positions to find occurrence of " a " first . ; if we found occurrence of " a " . ; then go through all the positions to find occurrence of " b " . ; if we do found " b " at index j then add it to already existed substring . ; if we found occurrence of " b " . ; now add string " b " to already existed substring . ; If current substring is not included already . ; put any non negative integer to make this string as already existed . ; make substring null . ; return answer . ; Driver program for above function .
#include <bits/stdc++.h> NEW_LINE using namespace std ; int numberOfDifferentSubstrings ( string s , string a , string b ) { int ans = 0 ; int ls = s . size ( ) , la = a . size ( ) , lb = b . size ( ) ; int x [ ls ] = { 0 } , y [ ls ] = { 0 } ; for ( int i = 0 ; i < ls ; i ++ ) { if ( s . substr ( i , la ) == a ) x [ i ] = 1 ; if ( s . substr ( i , lb ) == b ) y [ i ] = 1 ; } unordered_set < string > hash ; string curr_substr = " " ; for ( int i = 0 ; i < ls ; i ++ ) { if ( x [ i ] ) { for ( int j = i ; j < ls ; j ++ ) { if ( ! y [ j ] ) curr_substr += s [ j ] ; if ( y [ j ] ) { curr_substr += s . substr ( j , lb ) ; if ( hash . find ( curr_substr ) == hash . end ( ) ) ans ++ ; hash . insert ( curr_substr ) ; } } curr_substr = " " ; } } return ans ; } int main ( ) { string s = " codecppforfood " ; string begin = " c " ; string end = " d " ; cout << numberOfDifferentSubstrings ( s , begin , end ) << endl ; return 0 ; }