Skip to main content

Z Algorithm

Learn Z Algorithm (Strings, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

What is the Z Array? For a string s , the Z array's entry z[i] is the length of the longest substring starting at i that matches a PREFIX of s . By definition z[0] is usually left undefined/0 (comparing the whole string to itself is trivial and unused). For pattern matching, build the Z array of pattern + '#' + text (a separator character not in either string) - any position in the "text" section where z[i] == pattern.length() marks a match.

More lessons in Strings