def naive(string):
    z = [0 for _ in string]
    z[0] = len(string)
    for i in range(1, len(string)):
        for j in range(0, len(string)):
            if i+j == len(string) or string[i+j] != string[j]:
                z[i] = j
                break
    return z


def naive2(string):
    z = [0 for _ in string]
    z[0] = len(string)
    for i in range(1, len(string)):
        z[i] = compare(string, i, len(string))
    return z


def compare(string, i, end):
    for j in range(end):
        if i+j == end or string[i+j] != string[j]:
            return j


def gusfield(string):
    z = [0 for _ in string]
    z[0] = len(string)
    r = 0
    l = 0
    for i in range(1, len(string)):
        if i == 1:  # base case
            z[1] = compare(string, i, len(string))
            if z[1] > 0:
                r = z[1] + 1
                l = 1
        elif i > r: # Case 1
            z[i] = compare(string, i, len(string))
            if z[i] > 0:
                q = i + z[i]
                r = q - 1
                l = i
        elif i <= r:  # Case 2
            if z[i-l] < r-i:  # 2a
                print(f"{i} is a case 2a")
                z[i] = z[i-l]
            else:  # 2b
                print(f"{i} is a case 2b")
                q = compare(string, i, len(string))
                z[i] = q
                r = q
                l = i

    print(f"{l=}, {r=}")
    return z


def main():
    string = "ababacababa"
    print(naive2(string))
    print("="*15)
    print(gusfield(string))

if __name__ == '__main__':
    main()