Count of distinct substrings of a string using Suffix Trie | A C ++ program to find the count of distinct substring of a string using trie data structure ; A Suffix Trie ( A Trie of all suffixes ) Node ; SuffixTrieNode ( ) Constructor ; Initialize all child pointers as NULL ; A recursive function to insert a suffix of the s in subtree rooted with this node ; If string has more characters ; Find the first character and convert it into 0 - 25 range . ; If there is no edge for this character , add a new edge ; Recur for next suffix ; A Trie of all suffixes ; Constructor ( Builds a trie of suffies of the given text ) ; Consider all suffixes of given string and insert them into the Suffix Trie using recursive function insertSuffix ( ) in SuffixTrieNode class ; A recursive function to count nodes in trie ; If all characters of pattern have been processed , ; if children is not NULL then find count of all nodes in this subtrie ; return count of nodes of subtrie and plus 1 because of node 's own count ; method to count total nodes in suffix trie ; Returns count of distinct substrings of str ; Construct a Trie of all suffixes ; Return count of nodes in Trie of Suffixes ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE #define MAX_CHAR  26 NEW_LINE using namespace std ; class SuffixTrieNode { public : SuffixTrieNode * children [ MAX_CHAR ] ; { for ( int i = 0 ; i < MAX_CHAR ; i ++ ) children [ i ] = NULL ; } void SuffixTrieNode :: insertSuffix ( string s ) { if ( s . length ( ) > 0 ) { char cIndex = s . at ( 0 ) - ' a ' ; if ( children [ cIndex ] == NULL ) children [ cIndex ] = new SuffixTrieNode ( ) ; children [ cIndex ] -> insertSuffix ( s . substr ( 1 ) ) ; } } class SuffixTrie { SuffixTrieNode * root ; int _countNodesInTrie ( SuffixTrieNode * ) ; public : SuffixTrie ( string s ) { root = new SuffixTrieNode ( ) ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) root -> insertSuffix ( s . substr ( i ) ) ; } int SuffixTrie :: _countNodesInTrie ( SuffixTrieNode * node ) { if ( node == NULL ) return 0 ; int count = 0 ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { if ( node -> children [ i ] != NULL ) count += _countNodesInTrie ( node -> children [ i ] ) ; } return ( 1 + count ) ; } int countNodesInTrie ( ) { return _countNodesInTrie ( root ) ; } } ; int countDistinctSubstring ( string str ) { SuffixTrie sTrie ( str ) ; return sTrie . countNodesInTrie ( ) ; } int main ( ) { string str = " ababa " ; cout << " Count ▁ of ▁ distinct ▁ substrings ▁ is ▁ " << countDistinctSubstring ( str ) ; return 0 ; }