Dada una array de strings arr[] , la tarea es encontrar el recuento de distintas strings presentes en la array utilizando la función hash polinomial rodante .
Ejemplos:
Entrada: arr[] = { “abcde”, “abcce”, “abcdf”, “abcde”, “abcdf” }
Salida: 3
Explicación:
las distintas strings en la array son { “abcde”, “abcce”, “abcdf” }.
Por lo tanto, la salida requerida es 3.Entrada: arr[] = { “ab”, “abc”, “abcd”, “abcde”, “a” }
Salida: 5
Explicación:
las distintas strings en la array son { “abcde”, “abcd”, “abc” , “ab”, “a” }.
Por lo tanto, la salida requerida es 5.
Enfoque: El problema se puede resolver usando Hashing . La idea es usar la función hash rodante para calcular el valor hash de todas las strings de la array y almacenarlo en otra array, digamos Hash[] . Finalmente, imprima el recuento de elementos distintos en la array Hash[] . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos Hash[] , para almacenar el valor hash de todas las strings presentes en la array utilizando la función hash rodante.
- Inicialice una variable, digamos cntElem , para almacenar el recuento de strings distintas presentes en la array.
- Recorre la array arr[] . Para cada string encontrada, calcule el valor hash de esa string y guárdelo en la array hash[] .
- Ordene la array hash[] .
- Atraviesa la array hash[] . Para cada elemento de la array, compruebe si hash[i] y hash[i – 1] son iguales o no. Si se encuentra que es falso, incremente cntElem en 1 .
- Finalmente, imprima el valor de cntElem .
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 find the hash value
// of a string
long long compute_hash(string str)
{
int p = 31;
int MOD = 1e9 + 7;
long long hash_val = 0;
long long mul = 1;
// Traverse the string
for (char ch : str) {
// Update hash_val
hash_val
= (hash_val + (ch - 'a' + 1) * mul)
% MOD;
// Update mul
mul = (mul * p) % MOD;
}
// Return hash_val of str
return hash_val;
}
// Function to find the count of distinct
// strings present in the given array
int distinct_str(vector<string>& arr, int n)
{
// Store the hash values of
// the strings
vector<long long> hash(n);
// Traverse the array
for (int i = 0; i < n; i++) {
// Stores hash value of arr[i]
hash[i] = compute_hash(arr[i]);
}
// Sort hash[] array
sort(hash.begin(), hash.end());
// Stores count of distinct
// strings in the array
int cntElem = 1;
// Traverse hash[] array
for (int i = 1; i < n; i++) {
if (hash[i] != hash[i - 1]) {
// Update cntElem
cntElem++;
}
}
return cntElem;
}
// Driver Code
int main()
{
vector<string> arr={"abcde","abcce","abcdf",abcde"};
int N = arr.size();
cout << distinct_str(arr, N) << endl;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.Arrays;
public class GFG {
// Function to find the hash value
// of a string
static int compute_hash(String str)
{
int p = 31;
int MOD = (int)1e9 + 7;
int hash_val = 0;
int mul = 1;
// Traverse the string
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
// Update hash_val
hash_val
= (hash_val + (ch - 'a' + 1) * mul)
% MOD;
// Update mul
mul = (mul * p) % MOD;
}
// Return hash_val of str
return hash_val;
}
// Function to find the count of distinct
// strings present in the given array
static int distinct_str(String arr[], int n)
{
// Store the hash values of
// the strings
int hash[] = new int [n];
// Traverse the array
for (int i = 0; i < n; i++) {
// Stores hash value of arr[i]
hash[i] = compute_hash(arr[i]);
}
// Sort hash[] array
Arrays.sort(hash);
// Stores count of distinct
// strings in the array
int cntElem = 1;
// Traverse hash[] array
for (int i = 1; i < n; i++) {
if (hash[i] != hash[i - 1]) {
// Update cntElem
cntElem++;
}
}
return cntElem;
}
// Driver Code
public static void main (String[] args)
{
String arr[] = { "abcde", "abcce",
"abcdf", "abcde" };
int N = arr.length;
System.out.println(distinct_str(arr, N));
}
}
// This code is contributed by AnkThon
Python3
# Python3 program to implement
# the above approach
# Function to find the hash value
# of a
def compute_hash(str):
p = 31
MOD = 10**9 + 7
hash_val = 0
mul = 1
# Traverse the
for ch in str:
# Update hash_val
hash_val = (hash_val + (ord(ch) - ord('a') + 1) * mul) % MOD
# Update mul
mul = (mul * p) % MOD
# Return hash_val of str
return hash_val
# Function to find the count of distinct
# strings present in the given array
def distinct_str(arr, n):
# Store the hash values of
# the strings
hash = [0]*(n)
# Traverse the array
for i in range(n):
# Stores hash value of arr[i]
hash[i] = compute_hash(arr[i])
# Sort hash[] array
hash = sorted(hash)
# Stores count of distinct
# strings in the array
cntElem = 1
# Traverse hash[] array
for i in range(1, n):
if (hash[i] != hash[i - 1]):
# Update cntElem
cntElem += 1
return cntElem
# Driver Code
if __name__ == '__main__':
arr=["abcde", "abcce","abcdf", "abcde"]
N = len(arr)
print(distinct_str(arr, N))
# This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the hash value
// of a string
static int compute_hash(string str)
{
int p = 31;
int MOD = (int)1e9 + 7;
int hash_val = 0;
int mul = 1;
// Traverse the string
for (int i = 0; i < str.Length; i++)
{
char ch = str[i];
// Update hash_val
hash_val = (hash_val + (ch -
'a' + 1) * mul) % MOD;
// Update mul
mul = (mul * p) % MOD;
}
// Return hash_val of str
return hash_val;
}
// Function to find the count of distinct
// strings present in the given array
static int distinct_str(string []arr, int n)
{
// Store the hash values of
// the strings
int []hash = new int [n];
// Traverse the array
for (int i = 0; i < n; i++)
{
// Stores hash value of arr[i]
hash[i] = compute_hash(arr[i]);
}
// Sort hash[] array
Array.Sort(hash);
// Stores count of distinct
// strings in the array
int cntElem = 1;
// Traverse hash[] array
for (int i = 1; i < n; i++)
{
if (hash[i] != hash[i - 1])
{
// Update cntElem
cntElem++;
}
}
return cntElem;
}
// Driver Code
public static void Main (String[] args)
{
string []arr = { "abcde", "abcce",
"abcdf", "abcde" };
int N = arr.Length;
Console.WriteLine(distinct_str(arr, N));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program to implement the above approach
// Function to find the hash value
// of a string
function compute_hash(str)
{
let p = 31;
let MOD = 1e9 + 7;
let hash_val = 0;
let mul = 1;
// Traverse the string
for (let i = 0; i < str.length; i++)
{
let ch = str[i];
// Update hash_val
hash_val = (hash_val + (ch.charCodeAt() - 'a'.charCodeAt() + 1) * mul) % MOD;
// Update mul
mul = (mul * p) % MOD;
}
// Return hash_val of str
return hash_val;
}
// Function to find the count of distinct
// strings present in the given array
function distinct_str(arr, n)
{
// Store the hash values of
// the strings
let hash = new Array(n);
// Traverse the array
for (let i = 0; i < n; i++)
{
// Stores hash value of arr[i]
hash[i] = compute_hash(arr[i]);
}
// Sort hash[] array
hash.sort(function(a, b){return a - b});
// Stores count of distinct
// strings in the array
let cntElem = 1;
// Traverse hash[] array
for (let i = 1; i < n; i++)
{
if (hash[i] != hash[i - 1])
{
// Update cntElem
cntElem++;
}
}
return cntElem;
}
let arr = [ "abcde", "abcce", "abcdf", "abcde" ];
let N = arr.length;
document.write(distinct_str(arr, N));
</script>
Producción:
3
Complejidad de tiempo: O(N * M), donde M es la longitud máxima de la string
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zhatab_saifi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA