Queries to check if string B exists as substring in string A | Python3 implementation of the approach ; Function to return the modular inverse using Fermat 's little theorem ; Function to generate hash ; To store prefix - sum of rolling hash ; Multiplier for different values of i ; Generating hash value for string b ; Generating prefix - sum of hash of a ; Function that returns true if the required sub - string in a is equal to b ; To store hash of required sub - string of A ; If i = 0 then requires hash value ; Required hash if i != 0 ; Comparing hash with hash of B ; Driver Code ; Generating hash ; Queries ; Perform queries
mod = 3803 NEW_LINE d = 26 NEW_LINE hash_b = 0 NEW_LINE hash_a = [ ] NEW_LINE mul = [ ] NEW_LINE def mi ( x ) : NEW_LINE INDENT global mod NEW_LINE p = mod - 2 NEW_LINE s = 1 NEW_LINE while p != 1 : NEW_LINE INDENT if p % 2 == 1 : NEW_LINE INDENT s = ( s * x ) % mod NEW_LINE DEDENT x = ( x * x ) % mod NEW_LINE p //= 2 NEW_LINE DEDENT return ( s * x ) % mod NEW_LINE DEDENT def genHash ( a , b ) : NEW_LINE INDENT global hash_b , hash_a , mul , d , mod NEW_LINE hash_a = [ 0 ] * len ( a ) NEW_LINE mul = [ 0 ] * len ( a ) NEW_LINE for i in range ( len ( b ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT hash_b = ( hash_b * d + ( ord ( b [ i ] ) - 97 ) ) % mod NEW_LINE DEDENT mul [ 0 ] = 1 NEW_LINE hash_a [ 0 ] = ( ord ( a [ 0 ] ) - 97 ) % mod NEW_LINE for i in range ( 1 , len ( a ) ) : NEW_LINE INDENT mul [ i ] = ( mul [ i - 1 ] * d ) % mod NEW_LINE hash_a [ i ] = ( hash_a [ i - 1 ] + mul [ i ] * ( ord ( a [ i ] ) - 97 ) ) % mod NEW_LINE DEDENT DEDENT def checkEqual ( i , len_a , len_b ) : NEW_LINE INDENT global hash_b , hash_a , mul , d , mod NEW_LINE x = - 1 NEW_LINE if i == 0 : NEW_LINE INDENT x = hash_a [ len_b - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT x = ( hash_a [ i + len_b - 1 ] - hash_a [ i - 1 ] + 2 * mod ) % mod NEW_LINE x = ( x * mi ( mul [ i ] ) ) % mod NEW_LINE DEDENT if x == hash_b : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = " abababababa " NEW_LINE b = " aba " NEW_LINE genHash ( a , b ) NEW_LINE queries = [ 0 , 1 , 2 , 3 ] NEW_LINE q = len ( queries ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT if checkEqual ( queries [ i ] , len ( a ) , len ( b ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT DEDENT