Dada una string, cuente todas las substrings distintas de la string dada.
Ejemplos:
Input : abcd Output : abcd abc ab a bcd bc b cd c d All Elements are Distinct Input : aaa Output : aaa aa a aa a a All elements are not Distinct
Requisito previo: imprimir subarreglos de un arreglo dado
. La idea es usar una tabla hash ( HashSet en Java) para almacenar todas las substrings generadas. Finalmente devolvemos el tamaño del HashSet.
C++
// C++ program to count all distinct substrings in a string
#include<bits/stdc++.h>
using namespace std;
int distinctSubstring(string str)
{
// Put all distinct substring in a HashSet
set<string> result ;
// List All Substrings
for (int i = 0; i <= str.length(); i++)
{
for (int j = 1; j <= str.length()-i; j++)
{
// Add each substring in Set
result.insert(str.substr(i, j));
}
}
// Return size of the HashSet
return result.size();
}
// Driver Code
int main()
{
string str = "aaaa";
cout << (distinctSubstring(str));
}
// This code is contributed by Rajput-Ji
Java
// Java program to count all distinct substrings in a string
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class DistinctSubstring {
public static int distinctSubstring(String str)
{
// Put all distinct substring in a HashSet
Set<String> result = new HashSet<String>();
// List All Substrings
for (int i = 0; i <= str.length(); i++) {
for (int j = i + 1; j <= str.length(); j++) {
// Add each substring in Set
result.add(str.substring(i, j));
}
}
// Return size of the HashSet
return result.size();
}
// Driver Code
public static void main(String[] args)
{
String str = "aaaa";
System.out.println(distinctSubstring(str));
}
}
Python3
# Python3 program to count all distinct substrings in a string def distinctSubstring(str): # Put all distinct substring in a HashSet result = set() # List All Substrings for i in range(len(str)+1): for j in range( i + 1, len(str)+1): # Add each substring in Set result.add(str[i:j]); # Return size of the HashSet return len(result); # Driver Code if __name__ == '__main__': str = "aaaa"; print(distinctSubstring(str)); # This code has been contributed by 29AjayKumar
C#
// C# program to count all distinct
// substrings in a string
using System;
using System.Collections.Generic;
class DistinctSubstring
{
public static int distinctSubstring(String str)
{
// Put all distinct substring in a HashSet
HashSet<String> result = new HashSet<String>();
// List All Substrings
for (int i = 0; i <= str.Length; i++)
{
for (int j = i + 1; j <= str.Length; j++)
{
// Add each substring in Set
result.Add(str.Substring(i, j - i));
}
}
// Return size of the HashSet
return result.Count;
}
// Driver Code
public static void Main(String[] args)
{
String str = "aaaa";
Console.WriteLine(distinctSubstring(str));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to count all distinct substrings in a string
function distinctSubstring(str)
{
// Put all distinct substring in a HashSet
let result = new Set();
// List All Substrings
for (let i = 0; i <= str.length; i++) {
for (let j = i + 1; j <= str.length; j++) {
// Add each substring in Set
result.add(str.substring(i, j));
}
}
// Return size of the HashSet
return result.size;
}
// Driver Code
let str = "aaaa";
document.write(distinctSubstring(str));
// This code is contributed by patel2127
</script>
Producción
4
Complejidad de Tiempo: O(n 3 logn)
Espacio Auxiliar: O(n), ya que se ha tomado n espacio extra.
¿Cómo imprimir las distintas substrings?
C++
// C++ program to count all distinct
// substrings in a string
#include <bits/stdc++.h>
using namespace std;
set<string> distinctSubstring(string str)
{
// Put all distinct substrings
// in the Hashset
set<string> result;
// List all substrings
for(int i = 0; i <= str.length(); i++)
{
for(int j = i + 1; j <= str.length(); j++)
{
// Add each substring in Set
result.insert(str.substr(i, j));
}
}
// Return the hashset
return result;
}
// Driver code
int main()
{
string str = "aaaa";
set<string> subs = distinctSubstring(str);
cout << "Distinct Substrings are: \n";
for(auto i : subs)
cout << i << endl;
}
// This code is contributed by Ronak Mangal
Java
// Java program to count all distinct substrings in a string
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class DistinctSubstring {
public static Set<String> distinctSubstring(String str)
{
// Put all distinct substring in a HashSet
Set<String> result = new HashSet<String>();
// List All Substrings
for (int i = 0; i <= str.length(); i++) {
for (int j = i + 1; j <= str.length(); j++) {
// Add each substring in Set
result.add(str.substring(i, j));
}
}
// Return the HashSet
return result;
}
// Driver Code
public static void main(String[] args)
{
String str = "aaaa";
Set<String> subs = distinctSubstring(str);
System.out.println("Distinct Substrings are: ");
for (String s : subs) {
System.out.println(s);
}
}
}
Python3
# Python3 program to count all distinct
# substrings in a string
def distinctSubstring(str):
# Put all distinct substring in a HashSet
result = set();
# List All Substrings
for i in range(len(str)):
for j in range(i + 1, len(str) + 1):
# Add each substring in Set
result.add(str[i:j]);
# Return the HashSet
return result;
# Driver Code
if __name__ == '__main__':
str = "aaaa";
subs = distinctSubstring(str);
print("Distinct Substrings are: ");
for s in subs:
print(s);
# This code is contributed by 29AjayKumar
C#
// C# program to count all distinct
// substrings in a string
using System;
using System.Collections.Generic;
class GFG
{
public static HashSet<String> distinctSubstring(String str)
{
// Put all distinct substring in a HashSet
HashSet<String> result = new HashSet<String>();
// List All Substrings
for (int i = 0; i <= str.Length; i++)
{
for (int j = i + 1; j <= str.Length; j++)
{
// Add each substring in Set
result.Add(str.Substring(i, j - i));
}
}
// Return the HashSet
return result;
}
// Driver Code
public static void Main(String[] args)
{
String str = "aaaa";
HashSet<String> subs = distinctSubstring(str);
Console.WriteLine("Distinct Substrings are: ");
foreach (String s in subs)
{
Console.WriteLine(s);
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to count all distinct
// substrings in a string
function distinctSubstring(str)
{
// Put all distinct substrings
// in the Hashset
let result = new Set();
// List all substrings
for(let i = 0; i <= str.length; i++)
{
for(let j = i + 1; j <= str.length; j++)
{
// Add each substring in Set
result.add(str.substring(i, i+j));
}
}
// Return the hashset
return result;
}
// Driver code
let str = "aaaa";
let subs = distinctSubstring(str);
document.write("Distinct Substrings are: ","</br>");
for(let i of subs)
document.write(i,"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
Distinct Substrings are: a aa aaa aaaa
Complejidad de Tiempo: O(n 3 logn)
Espacio Auxiliar: O(n)
Optimización:
podemos optimizar aún más el código anterior. La función substr() funciona en tiempo lineal. Podemos usar agregar el carácter actual a la substring anterior para obtener la substring actual.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of
// valid sub-strings
void printSubstrings(string s)
{
// To store distinct output substrings
unordered_set<string> us;
// Traverse through the given string and
// one by one generate substrings beginning
// from s[i].
for (int i = 0; i < s.size(); ++i) {
// One by one generate substrings ending
// with s[j]
string ss = "";
for (int j = i; j < s.size(); ++j) {
ss = ss + s[j];
us.insert(ss);
}
}
// Print all substrings one by one
for (auto s : us)
cout << s << " ";
}
// Driver code
int main()
{
string str = "aaabc";
printSubstrings(str);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the count of
// valid sub-Strings
static void printSubStrings(String s)
{
// To store distinct output subStrings
HashSet<String> us = new HashSet<String>();
// Traverse through the given String and
// one by one generate subStrings beginning
// from s[i].
for (int i = 0; i < s.length(); ++i)
{
// One by one generate subStrings ending
// with s[j]
String ss = "";
for (int j = i; j < s.length(); ++j)
{
ss = ss + s.charAt(j);
us.add(ss);
}
}
// Print all subStrings one by one
for (String str : us)
System.out.print(str + " ");
}
// Driver code
public static void main(String[] args)
{
String str = "aaabc";
printSubStrings(str);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return the count of # valid sub-Strings def printSubStrings(s): # To store distinct output subStrings us = set(); # Traverse through the given String and # one by one generate subStrings beginning # from s[i]. for i in range(len(s)): # One by one generate subStrings ending # with s[j] ss = ""; for j in range(i, len(s)): ss = ss + s[j]; us.add(ss); # Print all subStrings one by one for str in us: print(str, end=" "); # Driver code if __name__ == '__main__': str = "aaabc"; printSubStrings(str); # This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the count of
// valid sub-Strings
static void printSubStrings(String s)
{
// To store distinct output subStrings
HashSet<String> us = new HashSet<String>();
// Traverse through the given String and
// one by one generate subStrings
// beginning from s[i].
for (int i = 0; i < s.Length; ++i)
{
// One by one generate subStrings
// ending with s[j]
String ss = "";
for (int j = i; j < s.Length; ++j)
{
ss = ss + s[j];
us.Add(ss);
}
}
// Print all subStrings one by one
foreach (String str in us)
Console.Write(str + " ");
}
// Driver code
public static void Main(String[] args)
{
String str = "aaabc";
printSubStrings(str);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of
// valid sub-strings
function printSubstrings(s)
{
// To store distinct output substrings
let us=new Set();
// Traverse through the given string and
// one by one generate substrings beginning
// from s[i].
for (let i = 0; i < s.length; ++i) {
// One by one generate substrings ending
// with s[j]
let ss = "";
for (let j = i; j < s.length; ++j) {
ss = ss + s[j];
us.add(ss);
}
}
// Print all substrings one by one
for (let s of us.values())
document.write(s+" ");
}
// Driver Code
let str = "aaabc";
printSubstrings(str);
// This code is contributed by unknown2108
</script>
Producción
bc b abc ab aabc aa aaa c a aaab aab aaabc
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n)
Optimización del espacio utilizando la estructura de datos Trie (cuando solo necesitamos contar substrings distintas)
Los enfoques anteriores hacen uso de hashing que puede conducir a un límite de memoria excedido (MLE) en el caso de strings muy grandes. La complejidad espacial aproximada de ellos es alrededor de O (n ^ 3) ya que puede haber n (n + 1)/2 substrings que es alrededor de O (n ^ 2) y cada substring puede tener al menos 1 longitud o n longitud, es decir O(n/2) caso promedio. Esto hace que la complejidad total del espacio sea O(n^3).
Podemos mejorar esto usando Trie. La idea es insertar el personaje que aún no está presente en el Trie. Y cuando ocurre tal suma, sabemos que esta string está ocurriendo por primera vez y, por lo tanto, la imprimimos. Y si algunos caracteres de la string ya están presentes, simplemente pasamos al siguiente Node sin leerlos, lo que nos ayuda a ahorrar espacio.
La complejidad de tiempo para este enfoque es O(n^2) similar al enfoque anterior pero el espacio se reduce a O(n)*26.
Implementación del enfoque anterior: –
C++
#include <bits/stdc++.h>
using namespace std;
class TrieNode {
public:
bool isWord;
TrieNode* child[26];
TrieNode()
{
isWord = 0;
for (int i = 0; i < 26; i++) {
child[i] = 0;
}
}
};
int countDistinctSubstring(string str)
{
TrieNode* head = new TrieNode();
// will hold the count of unique substrings
int count = 0;
// included count of substr " "
for (int i = 0; i < str.length(); i++) {
TrieNode* temp = head;
for (int j = i; j < str.length(); j++) {
// when char not present add it to the trie
if (temp->child[str[j] - 'a'] == NULL) {
temp->child[str[j] - 'a'] = new TrieNode();
temp->isWord = 1;
count++;
}
// move on to the next char
temp = temp->child[str[j] - 'a'];
}
}
return count;
}
int main()
{
int count = countDistinctSubstring("aaabc");
cout << "Count of Distinct Substrings: " << count
<< endl;
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
static class TrieNode {
TrieNode children[];
boolean isEnd;
TrieNode()
{
this.children = new TrieNode[26];
this.isEnd = false;
}
}
static TrieNode root = new TrieNode();
static void insert(String str)
{
TrieNode cur = root;
for (char ch : str.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
cur.children[idx] = new TrieNode();
cur = cur.children[idx];
}
cur.isEnd = true;
}
public static int distinctSubstringCount(String str)
{
// will hold the count of unique substrings
int cnt = 0;
for (int i = 0; i <= str.length(); i++) {
// start from root of trie each time as new
// starting point
TrieNode temp = root;
for (int j = i; j < str.length(); j++) {
char ch = str.charAt(j);
// when char not present add it to the trie
if (temp.children[ch - 'a'] == null) {
temp.children[ch - 'a']
= new TrieNode();
temp.isEnd = true;
cnt++;
}
// move on to the next char
temp = temp.children[ch - 'a'];
}
}
return cnt;
}
public static void main(String[] args)
{
int cnt = distinctSubstringCount("aaa");
System.out.println("Count of distinct substrings - "
+ cnt);
}
}
Producción
Count of Distinct Substrings: 12
Complejidad temporal: O(n 2 )
Complejidad espacial: O(n)
Publicación traducida automáticamente
Artículo escrito por bilal-hungund y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA