Count Distinct Strings present in an array using Polynomial rolling hash function | Java 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
import java . util . Arrays ; public class GFG { static int compute_hash ( String str ) { int p = 31 ; int MOD = ( int ) 1e9 + 7 ; int hash_val = 0 ; int mul = 1 ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) { char ch = str . charAt ( i ) ; hash_val = ( hash_val + ( ch - ' a ' + 1 ) * mul ) % MOD ; mul = ( mul * p ) % MOD ; } return hash_val ; } static int distinct_str ( String arr [ ] , int n ) { int hash [ ] = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { hash [ i ] = compute_hash ( arr [ i ] ) ; } Arrays . sort ( hash ) ; int cntElem = 1 ; for ( int i = 1 ; i < n ; i ++ ) { if ( hash [ i ] != hash [ i - 1 ] ) { cntElem ++ ; } } return cntElem ; } public static void main ( String [ ] args ) { String arr [ ] = { " abcde " , " abcce " , " abcdf " , " abcde " } ; int N = arr . length ; System . out . println ( distinct_str ( arr , N ) ) ; } }