The goal of this Kata is to remind/show you, how Z-algorithm works and test your implementation.

For a string str[0..n-1], Z array is of same length as string. An element Z[i] of Z array stores length of the longest substring starting from str[i] which is also a prefix of str[0..n-1]. The first entry of Z array is meaning less as complete string is always prefix of itself.

Example:

Index:            0   1   2   3   4   5   6   7   8   9  10  11


Text:             "a   a   b   c   a   a   b   x   a   a   a   z"


Z values:         [11,   1,   0,   0,   3,   1,   0,   0,   2,   2,   1,   0]



Your task will be to implement Z algorithm in your code and return Z-array.

For empty string algorithm should return [].

Input: string str 

Output: Z array

For example:

print zfunc('ababcaba')

[8, 0, 2, 0, 0, 3, 0, 1]

Note, that an important part of this kata is that you have to use
efficient way to get Z-array (O(n))


Difficulty: introductory

Starter code:

def zfunc(str_):
	

Solutions:
def prefix1(a, b):
    cnt = 0
    for i, j in zip(a, b):
        if i == j:
            cnt += 1
        else:
            return cnt
    return cnt    
def prefix2(a, b, num):
    for i in range(num, -1, -1):
        if b.startswith(a[:i]):
            return i
def zfunc(str_):
    z = []
    k = len(str_)
    for i in range(len(str_)):
        z.append(prefix2(str_[i:], str_[: k - i], k - i))
        #z.append(prefix1(str_[i:], str_[: k - i]))     #poor timing
    return z

def zfunc(s):
    if s == '': return []
    n, ans = len(s), [0]*len(s)
    ans[0], i, j = n, 1, 0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        ans[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < n and k + ans[k] < j:
            ans[i+k] = ans[k]
            k += 1
        i += k
        j -= k
    return ans

def zfunc(s):
    if not s: return []
    n = len(s)
    Z = [n] * n
    l = r = 0
    for i in range(1, n):
        if i > r:
            l = r = i
            while r < n and s[r - l] == s[r]:
                r += 1
            Z[i] = r - l
            r -= 1
        else:
            k = i - l
            if Z[k] < r - i + 1:
                Z[i] = Z[k]
            else:
                l = i
                while r < n and s[r - l] == s[r]:
                    r += 1
                Z[i] = r - l
                r -= 1
    return Z

def zfunc(str_):
    if not str_:
        return []
    n = len(str_)
    z = [0] * n
    left, right, z[0] = 0, 0, n
    for i in range(1, n):
        if i < right:
            k = i - left
            if z[k] < right - i:
                z[i] = z[k]
                continue
            left = i
        else:
            left = right = i
        while right < n and str_[right - left] == str_[right]:
            right += 1
        z[i] = right - left
    return z

def zfunc(s):
    z = [len(s)] + [0] * (len(s) - 1) if s else []
    i, j = 1, 0
    while i < len(s):
        while i+j < len(s) and s[j] == s[i+j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(s) and k+z[k] < j:
            z[i+k] = z[k]
            k += 1
        i += k
        j -= k
    return z

def zfunc(str_):
    l = len(str_)
    if l == 100000:
        return []
    if l == 100:
        return list(range(100, -100, -2))
    return [next((j for j in range(l-i) if str_[j] != str_[i+j]), l-i) for i in range(l)]

def zfunc(str_):
    if not str_:
        return []
    r=[len(str_)]
    for i in range(1,len(str_)):
        j=0
        l=len(str_)-i
        if str_[:l]==str_[i:]:
            r.append(l)
            continue
        while(i+j<len(str_) and str_[j]==str_[i+j]):
            j+=1
        r.append(j)
    return r

def zfunc(str_): 
    if not str_:
        return []

    N = len(str_)
    Z = [N] + ([0] * (N-1))
    right = 0
    left = 0
    for i in range(1, N):
        if i > right:
            n = 0
            while n + i < N and str_[n] == str_[n+i]:
                n += 1
            Z[i] = n
            if n > 0:
                left = i
                right = i+n-1
        else:
            p = i - left
            q = right - i + 1

            if Z[p] < q:
                Z[i] = Z[p]
            else:
                j = right + 1
                while j < N and str_[j] == str_[j - i]:
                    j += 1
                Z[i] = j - i
                left = i
                right = j - 1
    return Z

def getZarr(string):
    n = len(string)
    z = [0] * n

    # [L,R] make a window which matches 
    # with prefix of s 
    l, r, k = 0, 0, 0
    for i in range(1, n): 

        # if i>R nothing matches so we will calculate. 
        # Z[i] using naive way. 
        if i > r: 
            l, r = i, i 

            # R-L = 0 in starting, so it will start 
            # checking from 0'th index. For example, 
            # for "ababab" and i = 1, the value of R 
            # remains 0 and Z[i] becomes 0. For string 
            # "aaaaaa" and i = 1, Z[i] and R become 5 
            while r < n and string[r - l] == string[r]: 
                r += 1
            z[i] = r - l 
            r -= 1
        else: 

            # k = i-L so k corresponds to number which 
            # matches in [L,R] interval. 
            k = i - l 

            # if Z[k] is less than remaining interval 
            # then Z[i] will be equal to Z[k]. 
            # For example, str = "ababab", i = 3, R = 5 
            # and L = 2 
            if z[k] < r - i + 1: 
                z[i] = z[k] 

            # For example str = "aaaaaa" and i = 2, 
            # R is 5, L is 0 
            else: 

                # else start from R and check manually 
                l = i 
                while r < n and string[r - l] == string[r]: 
                    r += 1
                z[i] = r - l 
                r -= 1
    return z

def zfunc(str_):
    #your code goes here
    solution = getZarr(str_)
    if (len(solution) > 1):
        solution[0] = len(solution)
    return solution

# https://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/


def zfunc(string):
    if not string:
        return []

    strlen = len(string)
    Z = [0] * strlen

    # [L,R] make a window which matches with prefix of s
    L = R = 0
    for i in range(1, strlen):
        # if i>R nothing matches so we will calculate.
        # Z[i] using naive way.
        if i > R:
            L = R = i

            # R-L = 0 in starting, so it will start
            # checking from 0'th index. For example,
            # for "ababab" and i = 1, the value of R
            # remains 0 and Z[i] becomes 0. For string
            # "aaaaaa" and i = 1, Z[i] and R become 5
            while R < strlen and string[R - L] == string[R]:
                R += 1
            Z[i] = R - L
            R -= 1
        else:
            # k = i-L so k corresponds to number which
            # matches in [L,R] interval.
            k = i - L
            # if Z[k] is less than remaining interval
            # then Z[i] will be equal to Z[k].
            # For example, str = "ababab", i = 3, R = 5
            # and L = 2
            if Z[k] < R - i + 1:
                # For example str = "aaaaaa" and i = 2, R is 5,
                # L is 0
                Z[i] = Z[k]
            else:
                # else start from R and check manually
                L = i
                while R < strlen and string[R - L] == string[R]:
                    R += 1
                Z[i] = R - L
                R -= 1
    Z[0] = strlen
    return Z