Count of distinct substrings of a string using Suffix Trie | 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 ; public 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
using System ; public class Suffix { public class SuffixTrieNode { static readonly int MAX_CHAR = 26 ; public SuffixTrieNode [ ] children = new SuffixTrieNode [ MAX_CHAR ] ; { for ( int i = 0 ; < ; ++ ) children [ i ] = null ; } public void insertSuffix ( String s ) { if ( s . Length > 0 ) { char cIndex = ( char ) ( s [ 0 ] - ' a ' ) ; if ( children [ cIndex ] == null ) children [ cIndex ] = new SuffixTrieNode ( ) ; children [ cIndex ] . insertSuffix ( s . Substring ( 1 ) ) ; } } } public class Suffix_trie { static readonly int MAX_CHAR = 26 ; public SuffixTrieNode root ; public Suffix_trie ( String s ) { root = new SuffixTrieNode ( ) ; for ( int i = 0 ; i < s . Length ; i ++ ) root . insertSuffix ( s . Substring ( i ) ) ; } public int _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 ) ; } public int countNodesInTrie ( ) { return _countNodesInTrie ( root ) ; } } static int ( ) { = new Suffix_trie ( str ) ; return sTrie . countNodesInTrie ( ) ; } public static void Main ( String [ ] args ) { String str = " ababa " ; Console . WriteLine ( " Count ▁ of ▁ distinct ▁ substrings ▁ is ▁ " + countDistinctSubstring ( str ) ) ; } }