Dada una string str , la tarea es encontrar el número de substrings distintas que se colocan consecutivamente en la string dada.
Ejemplos:
Entrada: str = “geeksgeeksforgeeks”
Salida: 2
Explicación:
geeksgeeks forgeeks -> {“geeks”}
g ee ksg ee ksforg ee ks -> {“e”}
Solo se considera una ocurrencia consecutiva de “e”.
Por lo tanto, dos substrings distintas {“geeks”, “e”} ocurren consecutivamente en la string.
Por lo tanto, la respuesta es 2.Entrada: s = “geeksforgeeks”
Salida: 1
Explicación:
g ee ksgeeksforgeeks -> {“e”, “e”}
Solo una substring {“e”} aparece consecutivamente en la string.
Enfoque ingenuo:
el enfoque más simple es generar todas las substrings posibles de la string dada y, para cada substring, encontrar el recuento de substrings en lo dado que ocurren consecutivamente en la string. Finalmente, imprima el conteo.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque Eficiente:
Para optimizar el enfoque anterior, la idea es utilizar Programación Dinámica .
Siga los pasos a continuación para resolver el problema:
- Si la longitud de la string no excede 1 , entonces no es posible encontrar substrings similares colocadas consecutivamente. Así que devuelve 0 como el conteo .
- De lo contrario, inicialice una tabla de memorización dp[] de dimensiones (N+1 * N+1) que se inicializa en 0 .
- Inicialice un conjunto unordered_set para almacenar las distintas substrings colocadas consecutivamente.
- Iterar desde el final de la string.
- Al atravesar la string, si se encuentra algún carácter repetido, se determinará dp[i][j] teniendo en cuenta el valor de dp calculado previamente, es decir, el recuento de substrings idénticas hasta dp[i+1][j+1] caracteres e incluyendo el personaje actual.
- Si el carácter no es similar, dp[i][j] se completará con 0.
- Las substrings similares se colocan juntas consecutivamente sin ningún otro carácter y serán iguales para la mayoría de los caracteres (j – i) . Por lo tanto, para substrings válidas, el valor dp[i][j] debe ser mayor que (j – i) . Almacene esas substrings en unordered_set que aparece la mayor cantidad de veces consecutivas.
- Finalmente, devuelva el tamaño de unordered_set como el recuento de distintas substrings colocadas consecutivamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the distinct substrings
// placed consecutively in the given string
int distinctSimilarSubstrings(string str)
{
// Length of the string
int n = str.size();
// If length of the string
// does not exceed 1
if (n <= 1) {
return 0;
}
// Initialize a DP-table
vector<vector<int> > dp(
n + 1, vector<int>(n + 1, 0));
// Stores the distinct substring
unordered_set<string> substrings;
// Iterate from end of the string
for (int j = n - 1; j >= 0; j--) {
// Iterate backward until
// dp table is all computed
for (int i = j - 1; i >= 0; i--) {
// If character at i-th index is
// same as character at j-th index
if (str[i] == str[j]) {
// Update dp[i][j] based on
// previously computed value
dp[i][j] = dp[i + 1][j + 1] + 1;
}
// Otherwise
else {
dp[i][j] = 0;
}
// Condition for consecutively
// placed similar substring
if (dp[i][j] >= j - i) {
substrings.insert(
str.substr(i, j - i));
}
}
}
// Return the count
return substrings.size();
}
// Driver Code
int main()
{
string str = "geeksgeeksforgeeks";
cout << distinctSimilarSubstrings(str);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.ArrayList;
class GFG{
// Function to count the distinct substrings
// placed consecutively in the given string
static int distinctSimilarSubstrings(String str)
{
// Length of the string
int n = str.length();
// If length of the string
// does not exceed 1
if (n <= 1)
return 0;
// Initialize a DP-table
long dp[][] = new long[n + 1][n + 1];
// Declaring ArrayList to store strings
ArrayList<String> list = new ArrayList<String>();
// Iterate from end of the string
for(int j = n - 1; j >= 0; j--)
{
// Iterate backward until
// dp table is all computed
for(int i = j - 1; i >= 0; i--)
{
// If character at i-th index is
// same as character at j-th index
if (str.charAt(i) == str.charAt(j))
{
// Update dp[i][j] based on
// previously computed value
dp[i][j] = dp[i + 1][j + 1] + 1;
}
// Otherwise
else
{
dp[i][j] = 0;
}
// Condition for consecutively
// placed similar substring
if (dp[i][j] >= j - i)
{
list.add(str.substring(j - i, i));
}
}
}
// Return the count
return list.size();
}
// Driver Code
public static void main(String[] args)
{
String str = "geeksforgeeks";
System.out.println(distinctSimilarSubstrings(str));
}
}
// This code is contributed by user_00
Python3
# Python3 program to implement # the above approach # Function to count the distinct substrings # placed consecutively in the given string def distinctSimilarSubstrings(str): # Length of the string n = len(str) # If length of the string # does not exceed 1 if(n <= 1): return 0 # Initialize a DP-table dp = [[0 for x in range(n + 1)] for y in range(n + 1)] # Stores the distinct substring substrings = set() # Iterate from end of the string for j in range(n - 1, -1, -1): # Iterate backward until # dp table is all computed for i in range(j - 1, -1, -1): # If character at i-th index is # same as character at j-th index if(str[i] == str[j]): # Update dp[i][j] based on # previously computed value dp[i][j] = dp[i + 1][j + 1] + 1 # Otherwise else: dp[i][j] = 0 # Condition for consecutively # placed similar substring if(dp[i][j] >= j - i): substrings.add(str[i : j - i]) # Return the count return len(substrings) # Driver Code str = "geeksgeeksforgeeks" # Function call print(distinctSimilarSubstrings(str)) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to count the distinct substrings
// placed consecutively in the given string
static int distinctSimilarSubstrings(string str)
{
// Length of the string
int n = str.Length;
// If length of the string
// does not exceed 1
if (n <= 1)
return 0;
// Initialize a DP-table
long[,] dp = new long[n + 1, n + 1];
// Declaring ArrayList to store strings
List<string> list = new List<string>();
// Iterate from end of the string
for(int j = n - 1; j >= 0; j--)
{
// Iterate backward until
// dp table is all computed
for(int i = j - 1; i >= 0; i--)
{
// If character at i-th index is
// same as character at j-th index
if (str[i] == str[j])
{
// Update dp[i][j] based on
// previously computed value
dp[i, j] = dp[i + 1, j + 1] + 1;
}
// Otherwise
else
{
dp[i, j] = 0;
}
// Condition for consecutively
// placed similar substring
if (dp[i, j] >= j - i)
{
list.Add(str.Substring(i, j - i));
}
}
}
// Return the count
return list.Count;
}
// Driver code
static void Main()
{
string str = "geeksforgeeks";
Console.WriteLine(distinctSimilarSubstrings(str));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to count the distinct substrings
// placed consecutively in the given string
function distinctSimilarSubstrings(str)
{
// Length of the string
var n = str.length;
// If length of the string
// does not exceed 1
if (n <= 1) {
return 0;
}
// Initialize a DP-table
var dp = Array.from(Array(n+1), ()=>Array(n+1).fill(0));
// Stores the distinct substring
var substrings = new Set();
// Iterate from end of the string
for (var j = n - 1; j >= 0; j--) {
// Iterate backward until
// dp table is all computed
for (var i = j - 1; i >= 0; i--) {
// If character at i-th index is
// same as character at j-th index
if (str[i] == str[j]) {
// Update dp[i][j] based on
// previously computed value
dp[i][j] = dp[i + 1][j + 1] + 1;
}
// Otherwise
else {
dp[i][j] = 0;
}
// Condition for consecutively
// placed similar substring
if (dp[i][j] >= j - i) {
substrings.add(str.substring(i, j));
}
}
}
// Return the count
return substrings.size;
}
// Driver Code
var str = "geeksgeeksforgeeks";
document.write( distinctSimilarSubstrings(str));
// This code is contributed by noob2000.
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por goodday451999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA