Count number of distinct substrings of a given length | Java implementation of above approach ; Function to find the required count ; Variable to the hash ; Finding hash of substring ( 0 , l - 1 ) using random number x ; Computing x ^ ( l - 1 ) ; Unordered set to add hash values ; Generating all possible hash values ; Print the result ; Driver Code
import java . util . * ; class GFG { static int x = 26 ; static int mod = 3001 ; static void CntSubstr ( char [ ] s , int l ) { int hash = 0 ; for ( int i = 0 ; i < l ; i ++ ) { hash = ( hash * x + ( s [ i ] - 97 ) ) % mod ; } int pow_l = 1 ; for ( int i = 0 ; i < l - 1 ; i ++ ) { pow_l = ( pow_l * x ) % mod ; } HashSet < Integer > result = new HashSet < Integer > ( ) ; result . add ( hash ) ; for ( int i = l ; i < s . length ; i ++ ) { hash = ( ( hash - pow_l * ( s [ i - l ] - 97 ) + 2 * mod ) * x + ( s [ i ] - 97 ) ) % mod ; result . add ( hash ) ; } System . out . println ( result . size ( ) ) ; } public static void main ( String [ ] args ) { String s = " abcba " ; int l = 2 ; CntSubstr ( s . toCharArray ( ) , l ) ; } }