def excess_entropy_fast(text: str, H_single, H_pair):
    """
    Calculates excess entropy of given string in O(n) time complexity

    :param text: an input tokenized string
    :param H_single: a function that calculates H(i, x_i)
    :param H_pair: a function that calculates H(x_i | x_{i-1}) = H(i, x_{i-1}, x_i)
    :return: a float value which is equal to excess entropy of given input string
    """
    n = len(text)
    EE = 0
    for i in range(n - 1):
        EE += H_single(i + 1, text[i + 1]) - H_pair(i + 1, text[i], text[i + 1])
    return EE