Numar_subsiruri_cu_arbori_de_sufixe

/// Un program C++ pentru a gasi numarul de subsiruri distincte
/// dintr-un sir folosind structuri de date de tip arbore
#include <bits/stdc++.h>
#define MAX_CHAR 26
using namespace std;

/// Nodul arborelui de sufixe (arbore cu toate sufixele)
class SuffixTrieNode
{
public:
	SuffixTrieNode *children[MAX_CHAR];
	SuffixTrieNode() /// Constructor
	{
		/// Initializarea tuturor pointerilor fii ca NULL
		for (int i = 0; i < MAX_CHAR; i++)
		children[i] = NULL;
	}
    /// O functie recursiva pentru a insera un sufix al lui s
    /// in subarborele cu radacina in acest nod
	void insertSuffix(string suffix);
};

/// Arborele tuturor sufixelor
class SuffixTrie
{
	SuffixTrieNode *root;
	int _countNodesInTrie(SuffixTrieNode *);
public:
	/// Constructor (Construiese un arbore de sufixe ale textului dat)
	SuffixTrie(string s)
	{
		root = new SuffixTrieNode();

		/// Sunt luate in considerare toate sufixele sirului dat si le insereaza
		/// in arborele de sufixe folosind functia recursiva
		/// insertSuffix() din clasa SuffixTrieNode
		for (int i = 0; i < s.length(); i++)
			root->insertSuffix(s.substr(i));
	}

	/// Metoda pentru numararea tuturor nodurilor din arborele de sufixe
	int countNodesInTrie() { return _countNodesInTrie(root); }
};

/// O functie recursiva pentru inserarea unui sufix al lui s
/// in subarborele cu radacina in acest nod
void SuffixTrieNode::insertSuffix(string s)
{
	/// Daca sirul are mai multe caractere
	if (s.length() > 0)
	{
		/// Gaseste primul caracter si-l converteste
		/// intr-un rang intre 0-25.
		char cIndex = s.at(0) - 'a';

        /// Daca nu exista nici o muchie pentru acest caracter,
        /// adaugam o noua muchie
        if (children[cIndex] == NULL)
			children[cIndex] = new SuffixTrieNode();
		/// Reapeleaza pentru urmatorul sufix
		children[cIndex]->insertSuffix(s.substr(1));
	}
}

/// Functia recursiva pentru numararea nodurilor din arbore
int SuffixTrie::_countNodesInTrie(SuffixTrieNode* node)
{
	/// Daca au fost prelucrate toate caracterele din model (tipar),
	if (node == NULL)
		return 0;

	int count = 0;
	for (int i = 0; i < MAX_CHAR; i++)
	{
		/// Daca fiul este nenul (NULL), atunci gasim numarul tuturor nodurilor
		/// din acest subarbore
		if (node->children[i] != NULL)
			count += _countNodesInTrie(node->children[i]);
	}

	/// Intoarce numarul de noduri din subarbore plus
	/// 1 deoarece numaram si numarul propriu al nodului
	return (1 + count);
}

/// Intoarce numarul de subsiruri distincte din str
int countDistinctSubstring(string str)
{
	/// Construieste arborele cu toate sufixele
	SuffixTrie sTrie(str);

	/// Intoarce numarul de noduri din arborele de sufixe
	return sTrie.countNodesInTrie();
}

/// Programul principal pentru testarea functiei de mai sus
int main()
{
	string str = "ababa";
	cout << "Numarul de subsiruri distincte este "
		<< countDistinctSubstring(str);
	return 0;
}