Z-Function Box Boundaries

Problem

Compute the Z-array, where z[i] is the length of the longest common prefix of s and s[i:]. The scan maintains a box [l, r] with r = l + z[l] - 1, reusing z[i - l] inside it. Return [z_array, max_right] where max_right is the largest right end of a non-empty box (z[l] > 0) reached while processing positions i >= 1, or -1 for the empty string.

Hint

Inside the current Z-box, z[i] starts at min(r - i + 1, z[i - l]) and only extends past r.

Test cases

case 1

in: ["aabcaabxaaaz"]

expected: [[12,1,0,0,3,1,0,0,2,2,1,0],10]

case 2

in: ["aaaa"]

expected: [[4,3,2,1],3]

case 3

in: ["abc"]

expected: [[3,0,0],0]

case 4

in: ["a"]

expected: [[1],0]

case 5

in: [""]

expected: [[],-1]

Starter codePython

def z_box_boundaries(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor