Count Distinct Strings present in an array using Polynomial rolling hash function | C ++ program to implement the above approach ; Function to find the hash value of a string ; Traverse the string ; Update hash_val ; Update mul ; Return hash_val of str ; Function to find the count of distinct strings present in the given array ; Store the hash values of the strings ; Traverse the array ; Stores hash value of arr [ i ] ; Sort hash [ ] array ; Stores count of distinct strings in the array ; Traverse hash [ ] array ; Update cntElem ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long compute_hash ( string str ) { int p = 31 ; int MOD = 1e9 + 7 ; long long hash_val = 0 ; long long mul = 1 ; for ( char ch : str ) { hash_val = ( hash_val + ( ch - ' a ' + 1 ) * mul ) % MOD ; mul = ( mul * p ) % MOD ; } return hash_val ; } int distinct_str ( vector < string > & arr , int n ) { vector < long long > hash ( n ) ; for ( int i = 0 ; i < n ; i ++ ) { hash [ i ] = compute_hash ( arr [ i ] ) ; } sort ( hash . begin ( ) , hash . end ( ) ) ; int cntElem = 1 ; for ( int i = 1 ; i < n ; i ++ ) { if ( hash [ i ] != hash [ i - 1 ] ) { cntElem ++ ; } } return cntElem ; } int main ( ) { vector < string > arr = { " abcde " , " abcce " , " abcdf " , abcde " } ; int N = arr . size ( ) ; cout << distinct_str ( arr , N ) << endl ; return 0 ; }