Count Distinct Strings present in an array using Polynomial rolling hash function | Function to find the hash value of a ; Traverse the ; 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
def compute_hash ( str ) : NEW_LINE INDENT p = 31 NEW_LINE MOD = 10 ** 9 + 7 NEW_LINE hash_val = 0 NEW_LINE mul = 1 NEW_LINE for ch in str : NEW_LINE INDENT hash_val = ( hash_val + ( ord ( ch ) - ord ( ' a ' ) + 1 ) * mul ) % MOD NEW_LINE mul = ( mul * p ) % MOD NEW_LINE DEDENT return hash_val NEW_LINE DEDENT def distinct_str ( arr , n ) : NEW_LINE INDENT hash = [ 0 ] * ( n ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT hash [ i ] = compute_hash ( arr [ i ] ) NEW_LINE DEDENT hash = sorted ( hash ) NEW_LINE cntElem = 1 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( hash [ i ] != hash [ i - 1 ] ) : NEW_LINE INDENT cntElem += 1 NEW_LINE DEDENT DEDENT return cntElem NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ " abcde " , " abcce " , " abcdf " , " abcde " ] NEW_LINE N = len ( arr ) NEW_LINE print ( distinct_str ( arr , N ) ) NEW_LINE DEDENT