Strings

ZList:

def buildZList(s: str) -> List[int]:
    """
    Used in pattern matching: buildZList(needle + '.' + haystack) and check for length(needle) in result

    Construct an array of length equal to the length of the input string
    Where the first number in the array is always 0
    and the rest of the number in the array represents the length of matched prefix of the input string

    example:
        buildZList('abababab') => [0,0,6,0,4,0,2,0]
        the substring string from index 2 to end is: 'ababab'
        which is the prefix of the input string

        buildZList('ba' + '.' + 'ababab') => [0 0 0 0 2 0 2 0 1]
        the number at index 4 is 2, which is the length of the needle, which means needle is in haystack

    Time Complexity: O(n)
    Space Complexity: O(n)
    :param s: str
    :return: List[int]
    """
    n = len(s)
    l, r = 0, 0
    z = [0] * n
    for i in range(1, n):
        if i > r:
            l, r = i, i
            while r < n and s[r - l] == s[r]:
                r += 1
            z[i] = r - l
            r -= 1
        else:
            if z[i - l] <= r - i:
                z[i] = z[i - l]
            else:
                l = i
                while r < n and s[r - l] == s[r]:
                    r += 1
                z[i] = r - l
                r -= 1

    return z