Count number of distinct substrings of a given length | Python3 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
x = 26 NEW_LINE mod = 3001 NEW_LINE def CntSubstr ( s , l ) : NEW_LINE INDENT hash = 0 ; NEW_LINE for i in range ( l ) : NEW_LINE INDENT hash = ( hash * x + ( ord ( s [ i ] ) - 97 ) ) % mod ; NEW_LINE DEDENT pow_l = 1 ; NEW_LINE for i in range ( l - 1 ) : NEW_LINE INDENT pow_l = ( pow_l * x ) % mod ; NEW_LINE DEDENT result = set ( ) ; NEW_LINE result . add ( hash ) ; NEW_LINE for i in range ( l , len ( s ) ) : NEW_LINE INDENT hash = ( ( hash - pow_l * ( ord ( s [ i - l ] ) - 97 ) + 2 * mod ) * x + ( ord ( s [ i ] ) - 97 ) ) % mod ; NEW_LINE result . add ( hash ) ; NEW_LINE DEDENT print ( len ( result ) ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " abcba " ; NEW_LINE l = 2 ; NEW_LINE CntSubstr ( s , l ) ; NEW_LINE DEDENT