Z-Function Maximum
MediumStringString Matching
Description
Compute the Z-function of the given string s (z[i] = length of the longest substring starting at i which matches a prefix of s). Return the maximum value over indices 1..n-1, or 0 if n ≤ 1.
Examples
Input:
s = "aaaaa"Output:
4Explanation:
Every suffix of 'aaaaa' matches a prefix; the longest non-self match is at index 1 with length 4.
Input:
s = "abcabc"Output:
3Explanation:
Suffix 'abc' at index 3 matches the prefix of length 3, so the max is 3.
Input:
s = "abcdef"Output:
0Explanation:
No proper suffix of 'abcdef' shares a prefix, so all nontrivial z values are 0.
Constraints
- •
1 ≤ s.length ≤ 10⁴ - •
s consists of lowercase English letters.