Dada una string de longitud n de caracteres alfabéticos en minúsculas, necesitamos contar el número total de substrings distintas de esta string. Ejemplos:
Input : str = “ababa” Output : 10 Total number of distinct substring are 10, which are, "", "a", "b", "ab", "ba", "aba", "bab", "abab", "baba" and "ababa"
La idea es crear un Trie de todos los sufijos de una string dada. Una vez que se restringe el Trie, nuestra respuesta es el número total de Nodes en el Trie construido. Por ejemplo, el siguiente diagrama representa Trie de todos los sufijos para «ababa». El número total de Nodes es 10, que es nuestra respuesta.
¿Como funciona esto?
- Cada ruta de raíz a Node de un Trie representa un prefijo de palabras presentes en Trie. Aquí nosotros las palabras son sufijos. Entonces cada Node representa un prefijo de sufijos.
- Cada substring de una string «str» es un prefijo de un sufijo de «str».
A continuación se muestra la implementación basada en la idea anterior.
C++
// A C++ program to find the count of distinct substring
// of a string using trie data structure
#include <bits/stdc++.h>
#define MAX_CHAR 26
using namespace std;
// A Suffix Trie (A Trie of all suffixes) Node
class SuffixTrieNode
{
public:
SuffixTrieNode *children[MAX_CHAR];
SuffixTrieNode() // Constructor
{
// Initialize all child pointers as NULL
for (int i = 0; i < MAX_CHAR; i++)
children[i] = NULL;
}
// A recursive function to insert a suffix of the s
// in subtree rooted with this node
void insertSuffix(string suffix);
};
// A Trie of all suffixes
class SuffixTrie
{
SuffixTrieNode *root;
int _countNodesInTrie(SuffixTrieNode *);
public:
// Constructor (Builds a trie of suffies of the given text)
SuffixTrie(string s)
{
root = new SuffixTrieNode();
// Consider all suffixes of given string and insert
// them into the Suffix Trie using recursive function
// insertSuffix() in SuffixTrieNode class
for (int i = 0; i < s.length(); i++)
root->insertSuffix(s.substr(i));
}
// method to count total nodes in suffix trie
int countNodesInTrie() { return _countNodesInTrie(root); }
};
// A recursive function to insert a suffix of the s in
// subtree rooted with this node
void SuffixTrieNode::insertSuffix(string s)
{
// If string has more characters
if (s.length() > 0)
{
// Find the first character and convert it
// into 0-25 range.
char cIndex = s.at(0) - 'a';
// If there is no edge for this character,
// add a new edge
if (children[cIndex] == NULL)
children[cIndex] = new SuffixTrieNode();
// Recur for next suffix
children[cIndex]->insertSuffix(s.substr(1));
}
}
// A recursive function to count nodes in trie
int SuffixTrie::_countNodesInTrie(SuffixTrieNode* node)
{
// If all characters of pattern have been processed,
if (node == NULL)
return 0;
int count = 0;
for (int i = 0; i < MAX_CHAR; i++)
{
// if children is not NULL then find count
// of all nodes in this subtrie
if (node->children[i] != NULL)
count += _countNodesInTrie(node->children[i]);
}
// return count of nodes of subtrie and plus
// 1 because of node's own count
return (1 + count);
}
// Returns count of distinct substrings of str
int countDistinctSubstring(string str)
{
// Construct a Trie of all suffixes
SuffixTrie sTrie(str);
// Return count of nodes in Trie of Suffixes
return sTrie.countNodesInTrie();
}
// Driver program to test above function
int main()
{
string str = "ababa";
cout << "Count of distinct substrings is "
<< countDistinctSubstring(str);
return 0;
}
Java
// A Java program to find the count of distinct substring
// of a string using trie data structure
public class Suffix
{
// A Suffix Trie (A Trie of all suffixes) Node
static class SuffixTrieNode
{
static final int MAX_CHAR = 26;
SuffixTrieNode[] children = new SuffixTrieNode[MAX_CHAR];
SuffixTrieNode() // Constructor
{
// Initialize all child pointers as NULL
for (int i = 0; i < MAX_CHAR; i++)
children[i] = null;
}
// A recursive function to insert a suffix of the s in
// subtree rooted with this node
void insertSuffix(String s)
{
// If string has more characters
if (s.length() > 0)
{
// Find the first character and convert it
// into 0-25 range.
char cIndex = (char) (s.charAt(0) - 'a');
// If there is no edge for this character,
// add a new edge
if (children[cIndex] == null)
children[cIndex] = new SuffixTrieNode();
// Recur for next suffix
children[cIndex].insertSuffix(s.substring(1));
}
}
}
// A Trie of all suffixes
static class Suffix_trie
{
static final int MAX_CHAR = 26;
SuffixTrieNode root;
// Constructor (Builds a trie of suffies of the given text)
Suffix_trie(String s) {
root = new SuffixTrieNode();
// Consider all suffixes of given string and insert
// them into the Suffix Trie using recursive function
// insertSuffix() in SuffixTrieNode class
for (int i = 0; i < s.length(); i++)
root.insertSuffix(s.substring(i));
}
// A recursive function to count nodes in trie
int _countNodesInTrie(SuffixTrieNode node)
{
// If all characters of pattern have been processed,
if (node == null)
return 0;
int count = 0;
for (int i = 0; i < MAX_CHAR; i++) {
// if children is not NULL then find count
// of all nodes in this subtrie
if (node.children[i] != null)
count += _countNodesInTrie(node.children[i]);
}
// return count of nodes of subtrie and plus
// 1 because of node's own count
return (1 + count);
}
// method to count total nodes in suffix trie
int countNodesInTrie()
{
return _countNodesInTrie(root);
}
}
// Returns count of distinct substrings of str
static int countDistinctSubstring(String str)
{
// Construct a Trie of all suffixes
Suffix_trie sTrie = new Suffix_trie(str);
// Return count of nodes in Trie of Suffixes
return sTrie.countNodesInTrie();
}
// Driver program to test above function
public static void main(String args[])
{
String str = "ababa";
System.out.println("Count of distinct substrings is "
+ countDistinctSubstring(str));
}
}
// This code is contributed by Sumit Ghosh
C#
// C# program to find the count of distinct substring
// of a string using trie data structure
using System;
public class Suffix
{
// A Suffix Trie (A Trie of all suffixes) Node
public class SuffixTrieNode
{
static readonly int MAX_CHAR = 26;
public SuffixTrieNode[] children = new SuffixTrieNode[MAX_CHAR];
public SuffixTrieNode() // Constructor
{
// Initialize all child pointers as NULL
for (int i = 0; i < MAX_CHAR; i++)
children[i] = null;
}
// A recursive function to insert a suffix of the s in
// subtree rooted with this node
public void insertSuffix(String s)
{
// If string has more characters
if (s.Length > 0)
{
// Find the first character and convert it
// into 0-25 range.
char cIndex = (char) (s[0] - 'a');
// If there is no edge for this character,
// add a new edge
if (children[cIndex] == null)
children[cIndex] = new SuffixTrieNode();
// Recur for next suffix
children[cIndex].insertSuffix(s.Substring(1));
}
}
}
// A Trie of all suffixes
public class Suffix_trie
{
static readonly int MAX_CHAR = 26;
public SuffixTrieNode root;
// Constructor (Builds a trie of suffies of the given text)
public Suffix_trie(String s)
{
root = new SuffixTrieNode();
// Consider all suffixes of given string and insert
// them into the Suffix Trie using recursive function
// insertSuffix() in SuffixTrieNode class
for (int i = 0; i < s.Length; i++)
root.insertSuffix(s.Substring(i));
}
// A recursive function to count nodes in trie
public int _countNodesInTrie(SuffixTrieNode node)
{
// If all characters of pattern have been processed,
if (node == null)
return 0;
int count = 0;
for (int i = 0; i < MAX_CHAR; i++)
{
// if children is not NULL then find count
// of all nodes in this subtrie
if (node.children[i] != null)
count += _countNodesInTrie(node.children[i]);
}
// return count of nodes of subtrie and plus
// 1 because of node's own count
return (1 + count);
}
// method to count total nodes in suffix trie
public int countNodesInTrie()
{
return _countNodesInTrie(root);
}
}
// Returns count of distinct substrings of str
static int countDistinctSubstring(String str)
{
// Construct a Trie of all suffixes
Suffix_trie sTrie = new Suffix_trie(str);
// Return count of nodes in Trie of Suffixes
return sTrie.countNodesInTrie();
}
// Driver program to test above function
public static void Main(String []args)
{
String str = "ababa";
Console.WriteLine("Count of distinct substrings is "
+ countDistinctSubstring(str));
}
}
// This code contributed by Rajput-Ji
Producción
Count of distinct substrings is 10
Complejidad de tiempo: O(n) , donde n es la longitud de la string.
Espacio Auxiliar: O(1)
Pronto discutiremos los enfoques basados en Suffix Array y Suffix Tree para este problema. Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA