q1. retry

def z_algo(pat, txt):
    input_str = pat + '$' + txt;
    n = len(input_str)
    z = [0]*n
    z[0] = n
    r = None
    l = None
    output_arr = []
    global match_count;
    match_count = 0;
    
    def compare(furthest_index, base_index, first_compare=True):
        global match_count
        transpose_index = None
        true_len = 0
        transpose_error = 0
        
        i=0;
        while(furthest_index + i < len(input_str)):
            #regular compare
            if(first_compare and input_str[base_index + i] == input_str[furthest_index + i]):
                i+=1;
            #check transposition error
            elif(furthest_index + i+1 <len(input_str) and input_str[base_index + i] == input_str[furthest_index + i + 1] and input_str[base_index + i + 1] == input_str[furthest_index + i]):
                transpose_error+=1;
                if(transpose_error >= 2):
                    break;
                else:
                    true_len = i;
                    transpose_index = furthest_index+i
                    i+=2;
            else:
                break;
            first_compare = True
        # check if pattern has been found
        if(furthest_index > len(pat) and (i + base_index >= len(pat) or true_len + base_index >= len(pat))):
            output_arr.append((furthest_index-base_index, transpose_index))
            match_count+=1;
            
        # return the actual z array value
        if(transpose_error > 0):
            return furthest_index + true_len;
        else:
            return furthest_index + i;
    
    k=1
    while(k<n):
        if(r == None or k>r):
            q = compare(k, 0)
            z[k] = q - k 
            if q - k > 0:
                r = q - 1
                l = k
        elif(z[k-l] < r-k + 1):
            q = compare(k + z[k-l], k - l, False)
            z[k]=z[k-l]
        elif(z[k-l] >= r-k + 1):
            q = compare(r + 1, r-k + 1)
            z[k]=q - k
            l = k
            r= q - 1
        k+=1;
    print(match_count)
    for item in output_arr:
        if item[1] is None:
            print(item[0] -len(pat))
        else:
            print(item[0] -len(pat), item[1] -len(pat))
        
z_algo('aa','aaaaaaaba')