def rabin_karp_factor(s, t, k):
    """Find a common factor by Rabin-Karp

    :param string s: haystack
    :param string t: needle
    :param int k: factor length
    :returns: (i, j) such that s[i:i + k] == t[j:j + k] or None.
              In case of tie, lexicographical minimum (i, j) is returned
    :complexity: O(len(s) + len(t)) in expected time,
                and O(len(s) + len(t) * k) in worst case
    """
    last_pos = pow(DOMAIN, k - 1) % PRIME
    pos = {}
    assert k > 0
    if len(s) < k or len(t) < k:
        return None
    hash_t = 0
    for j in range(k):         # store hashing values
        hash_t = (DOMAIN * hash_t + ord(t[j])) % PRIME
    for j in range(len(t) - k + 1):
        if hash_t in pos:
            pos[hash_t].append(j)
        else:
            pos[hash_t] = [j]
        if j < len(t) - k:
            hash_t = roll_hash(hash_t, ord(t[j]), ord(t[j + k]), last_pos)
    hash_s = 0
    for i in range(k):         # preprocessing
        hash_s = (DOMAIN * hash_s + ord(s[i])) % PRIME
    for i in range(len(s) - k + 1):
        if hash_s in pos:      # is this signature in s?
            for j in pos[hash_s]:
                if matches(s, t, i, j, k):
                    return (i, j)
        if i < len(s) - k:
            hash_s = roll_hash(hash_s, ord(s[i]), ord(s[i + k]), last_pos)
    return None
def rabin_karp_factor ( s , t , k ) : last_pos = pow ( DOMAIN , k - 1 ) % PRIME pos = { } assert k > 0 if len ( s ) < k or len ( t ) < k : return None hash_t = 0 for j in range ( k ) : hash_t = ( DOMAIN * hash_t + ord ( t [ j ] ) ) % PRIME for j in range ( len ( t ) - k + 1 ) : if hash_t in pos : pos [ hash_t ] . append ( j ) else : pos [ hash_t ] = [ j ] if j < len ( t ) - k : hash_t = roll_hash ( hash_t , ord ( t [ j ] ) , ord ( t [ j + k ] ) , last_pos ) hash_s = 0 for i in range ( k ) : hash_s = ( DOMAIN * hash_s + ord ( s [ i ] ) ) % PRIME for i in range ( len ( s ) - k + 1 ) : if hash_s in pos : for j in pos [ hash_s ] : if matches ( s , t , i , j , k ) : return ( i , j ) if i < len ( s ) - k : hash_s = roll_hash ( hash_s , ord ( s [ i ] ) , ord ( s [ i + k ] ) , last_pos ) return None
Find a common factor by Rabin-Karp

    :param string s: haystack
    :param string t: needle
    :param int k: factor length
    :returns: (i, j) such that s[i:i + k] == t[j:j + k] or None.
              In case of tie, lexicographical minimum (i, j) is returned
    :complexity: O(len(s) + len(t)) in expected time,
                and O(len(s) + len(t) * k) in worst case