Z-Function

Problem

Compute the Z-array of s, where z[i] is the length of the longest substring starting at i that matches a prefix of s.

Use the standard linear algorithm with the rightmost Z-box, reusing previously computed values while inside the box. Define z[0] as len(s).

Hint

Extending beyond the current Z-box is the only case that costs more than constant time.

case 1

in: ["aabcaabxaaaz"]

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

case 2

in: ["aaaa"]

expected: [4,3,2,1]

case 3

in: ["abc"]

expected: [3,0,0]

case 4

in: [""]

expected: []

case 5

in: ["a"]

expected: [1]

Starter codePython

def z_function(s):
    # Your code here
    pass

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