Count of Distinct Substrings occurring consecutively in a given String | C ++ Program to implement the above approach ; Function to count the distinct substrings placed consecutively in the given string ; Length of the string ; If length of the string does not exceed 1 ; Initialize a DP - table ; Stores the distinct substring ; Iterate from end of the string ; Iterate backward until dp table is all computed ; If character at i - th index is same as character at j - th index ; Update dp [ i ] [ j ] based on previously computed value ; Otherwise ; Condition for consecutively placed similar substring ; Return the count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int distinctSimilarSubstrings ( string str ) { int n = str . size ( ) ; if ( n <= 1 ) { return 0 ; } vector < vector < int > > dp ( n + 1 , vector < int > ( n + 1 , 0 ) ) ; unordered_set < string > substrings ; for ( int j = n - 1 ; j >= 0 ; j -- ) { for ( int i = j - 1 ; i >= 0 ; i -- ) { if ( str [ i ] == str [ j ] ) { dp [ i ] [ j ] = dp [ i + 1 ] [ j + 1 ] + 1 ; } else { dp [ i ] [ j ] = 0 ; } if ( dp [ i ] [ j ] >= j - i ) { substrings . insert ( str . substr ( i , j - i ) ) ; } } } return substrings . size ( ) ; } int main ( ) { string str = " geeksgeeksforgeeks " ; cout << distinctSimilarSubstrings ( str ) ; return 0 ; }