Z Algorithm — Pattern Matching
Practice this coding question on Coding Gurukul.
Problem statement
Given a text and a pattern, find every position where the full pattern occurs in the text using the Z algorithm. Compute Z values for pattern + separator + text, using a separator outside the lowercase alphabet. Print zero-based starting positions in increasing order. Include overlapping matches. Print -1 if there is no match, including when the pattern is longer than the text. Use O(text length + pattern length) time. Worked example In ababa, aba starts at indices 0 and 2. These matches overlap, so print both: 0 2.
Input format
First line: text. Second line: pattern.
Output format
Print space-separated match positions, or -1.
Constraints
1 <= text length, pattern length <= 200000; lowercase English letters only.
Sample input
ababa aba
Sample output
0 2
Sign in to run or submit a solution in C++, Java or Python.