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.