fork download 
  1. // A C++ program to find the count of distinct substring 
  2. // of a string using trie data structure 
  3. #include <bits/stdc++.h> 
  4. #define MAX_CHAR 26 
  5. using namespace std; 
  6.  
  7. // A Suffix Trie (A Trie of all suffixes) Node 
  8. class SuffixTrieNode 
  9. { 
  10. public: 
  11. 	SuffixTrieNode *children[MAX_CHAR]; 
  12. 	SuffixTrieNode() // Constructor 
  13. 	{ 
  14. 		// Initialize all child pointers as NULL 
  15. 		for (int i = 0; i < MAX_CHAR; i++) 
  16. 		children[i] = NULL; 
  17. 	} 
  18.  
  19. 	// A recursive function to insert a suffix of the s 
  20. 	// in subtree rooted with this node 
  21. 	void insertSuffix(string suffix); 
  22. }; 
  23.  
  24. // A Trie of all suffixes 
  25. class SuffixTrie 
  26. { 
  27. 	SuffixTrieNode *root; 
  28. 	int _countNodesInTrie(SuffixTrieNode *); 
  29. public: 
  30. 	// Constructor (Builds a trie of suffies of the given text) 
  31. 	SuffixTrie(string s) 
  32. 	{ 
  33. 		root = new SuffixTrieNode(); 
  34.  
  35. 		// Consider all suffixes of given string and insert 
  36. 		// them into the Suffix Trie using recursive function 
  37. 		// insertSuffix() in SuffixTrieNode class 
  38. 		for (int i = 0; i < s.length(); i++) 
  39. 			root->insertSuffix(s.substr(i)); 
  40. 	} 
  41.  
  42. 	// method to count total nodes in suffix trie 
  43. 	int countNodesInTrie() { return _countNodesInTrie(root); } 
  44. }; 
  45.  
  46. // A recursive function to insert a suffix of the s in 
  47. // subtree rooted with this node 
  48. void SuffixTrieNode::insertSuffix(string s) 
  49. { 
  50. 	// If string has more characters 
  51. 	if (s.length() > 0) 
  52. 	{ 
  53. 		// Find the first character and convert it 
  54. 		// into 0-25 range. 
  55. 		char cIndex = s.at(0) - 'a'; 
  56.  
  57. 		// If there is no edge for this character, 
  58. 		// add a new edge 
  59. 		if (children[cIndex] == NULL) 
  60. 			children[cIndex] = new SuffixTrieNode(); 
  61.  
  62. 		// Recur for next suffix 
  63. 		children[cIndex]->insertSuffix(s.substr(1)); 
  64. 	} 
  65. } 
  66.  
  67. // A recursive function to count nodes in trie 
  68. int SuffixTrie::_countNodesInTrie(SuffixTrieNode* node) 
  69. { 
  70. 	// If all characters of pattern have been processed, 
  71. 	if (node == NULL) 
  72. 		return 0; 
  73.  
  74. 	int count = 0; 
  75. 	for (int i = 0; i < MAX_CHAR; i++) 
  76. 	{ 
  77. 		// if children is not NULL then find count 
  78. 		// of all nodes in this subtrie 
  79. 		if (node->children[i] != NULL) 
  80. 			count += _countNodesInTrie(node->children[i]); 
  81. 	} 
  82.  
  83. 	// return count of nodes of subtrie and plus 
  84. 	// 1 because of node's own count 
  85. 	return (1 + count); 
  86. } 
  87.  
  88. // Returns count of distinct substrings of str 
  89. int countDistinctSubstring(string str) 
  90. { 
  91. 	// Construct a Trie of all suffixes 
  92. 	SuffixTrie sTrie(str); 
  93.  
  94. 	// Return count of nodes in Trie of Suffixes 
  95. 	return sTrie.countNodesInTrie(); 
  96. } 
  97.  
  98. // Driver program to test above function 
  99. int main() 
  100. { 
  101. 	string str = "ababa"; 
  102. 	cout << "Count of distinct substrings is "
  103. 		<< countDistinctSubstring(str); 
  104. 	return 0; 
  105. } 
  106.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
Count of distinct substrings is 10
https://ideone.com/1SsZyQ
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!