The Z-Function

The Z-function of s gives, for each position i, the length of the longest common prefix of s and s[i:]. By convention z[0] = 0.

For "aabxaab" the answer is [0, 1, 0, 0, 3, 1, 0].

The starter code extends a match letter by letter at every position. It is correct but too slow on repetitive strings.

Examples

Example 1

Input:

z_function('aabxaab')

Output:

[0, 1, 0, 0, 3, 1, 0]

Example 2

Input:

z_function('aaaa')

Output:

[0, 3, 2, 1]

Constraints

• 0 <= len(s) <= 200000
• Lower-case letters.