Count subsequence of length three in a given string | C ++ program to find number of occurrences of a subsequence of length 3 ; Function to find number of occurrences of a subsequence of length three in a string ; calculate length of string ; auxiliary array to store occurrences of first character ; auxiliary array to store occurrences of third character ; calculate occurrences of first character upto ith index from left ; calculate occurrences of third character upto ith index from right ; variable to store total number of occurrences ; loop to find the occurrences of middle element ; if middle character of subsequence is found in the string ; multiply the total occurrences of first character before middle character with the total occurrences of third character after middle character ; Driver code
#include <iostream> NEW_LINE using namespace std ; int findOccurrences ( string str , string substr ) { int n = str . length ( ) ; int preLeft [ n ] = { 0 } ; int preRight [ n ] = { 0 } ; if ( str [ 0 ] == substr [ 0 ] ) preLeft [ 0 ] ++ ; for ( int i = 1 ; i < n ; i ++ ) { if ( str [ i ] == substr [ 0 ] ) preLeft [ i ] = preLeft [ i - 1 ] + 1 ; else preLeft [ i ] = preLeft [ i - 1 ] ; } if ( str [ n - 1 ] == substr [ 2 ] ) preRight [ n - 1 ] ++ ; for ( int i = n - 2 ; i >= 0 ; i -- ) { if ( str [ i ] == substr [ 2 ] ) preRight [ i ] = preRight [ i + 1 ] + 1 ; else preRight [ i ] = preRight [ i + 1 ] ; } int counter = 0 ; for ( int i = 1 ; i < n - 1 ; i ++ ) { if ( str [ i ] == str [ 1 ] ) { int total = preLeft [ i - 1 ] * preRight [ i + 1 ] ; counter += total ; } } return counter ; } int main ( ) { string str = " GFGFGYSYIOIWIN " ; string substr = " GFG " ; cout << findOccurrences ( str , substr ) ; return 0 ; }