z_value.py

# Find the Z-array for the given string
def z_array(thatString):
    # length of that string
    lengthOfTheString = len(thatString)

    # make room for Z array; construct Z array
    z = [0] * lengthOfTheString
    # keep track of z-boxes
    # [l, r] makes a window which matches with prefix

    # initialize l, k, r = 0, 0, 0
    l = 0
    r = 0
    k = 0

    # loop (two loops basically)
    for i in range(0, lengthOfTheString):
        if i > r:
            l , r = i, i

            # r - l = 0 initially, so start checking from 0th index
            # If "aba" and i = 1, the value of r is 0 and Z[i] is 0
            # If "aaa" and i = 1, the value of r is 3 and Z[i] is 0
            while r < lengthOfTheString and thatString[r - l] == thatString[r]:
                # increase the right index of the Z-box
                r = r + 1
            # get the length of the z-box
            z[i] = r - l
            r = r - 1

        else:
            # k = i - l: k indicates the number which matches in [l, r]
            k = i - l
            # if z[k] is less than remaining interval then Z[i] = Z[k]
            if z[k] < r - i + 1:
                z[i] = z[k]
            # otherwise start from r and check normally
            else:
                l = i
                while r < lengthOfTheString and thatString[r - l] == thatString[r]:
                    # increase the right index of the Z-box
                    r = r + 1
                # get the length of the z-box
                z[i] = r - l
                r = r - 1

        print(z[i], end=' ')



def z_algorithm(theString):
    # Finding the length of concatenated string
    theStringLength = len(theString)
    # Invoke Z_array
    z = z_array(theString)



# Main Driver
if __name__ == "__main__":
    # givenString = "aaaa"
    givenString = input("Enter the string: ")

    for i in range(len(givenString)):
        print(givenString[i], end=' ')

    print()
    z_algorithm(givenString)