Count Distinct Strings present in an array using Polynomial rolling hash function | 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
function compute_hash ( str ) { let p = 31 ; let MOD = 1e9 + 7 ; let hash_val = 0 ; let mul = 1 ; for ( let i = 0 ; i < str . length ; i ++ ) { let ch = str [ i ] ; hash_val = ( hash_val + ( ch . charCodeAt ( ) - ' ' . charCodeAt ( ) + 1 ) * mul ) % MOD ; mul = ( mul * p ) % MOD ; } return hash_val ; } function distinct_str ( arr , n ) { let hash = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { hash [ i ] = compute_hash ( arr [ i ] ) ; } hash . sort ( function ( a , b ) { return a - b } ) ; let cntElem = 1 ; for ( let i = 1 ; i < n ; i ++ ) { if ( hash [ i ] != hash [ i - 1 ] ) { cntElem ++ ; } } return cntElem ; } let arr = [ " " , " " , " " , " " ] ; let N = arr . length ; document . write ( distinct_str ( arr , N ) ) ;