Word Near an Anchor

Hard

You are given a string text, two words word and anchor, and an integer reach. A position i is *lucky* if: - word starts at position i of text, that is, text[i : i + len(word)] == word; - there is a position j where anchor starts in text, with |i − j| ≤ reach. Occurrences may overlap, and j may equal i. Return all lucky positions in increasing order (0-based).

Example 1

text="catnapdogcatnapcat", word="cat", anchor="dog", reach=4 → [9]

cat starts at 0, 9 and 15, and dog starts at 6. Position 9 works (|9 − 6| = 3); 0 and 15 do not (distances 6 and 9).

Example 2

text="aaaa", word="aa", anchor="aaa", reach=1 → [0, 1, 2]

Occurrences may overlap. aa starts at 0, 1 and 2, aaa at 0 and 1. Every start of aa has a start of aaa within distance 1.

Example 3

text="hello", word="lo", anchor="xyz", reach=5 → []

Constraints

1 ≤ reach ≤ len(text) ≤ 5 · 10⁵
1 ≤ len(word), len(anchor) ≤ 5 · 10⁵
All strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Two Pointers String Binary Search String Matching Hash Function Rolling Hash

Similar problems

Anchor Near a Companion Medium Suffixes Echoing the Start Hard Phrase From Word Beginnings, Long Edition Hard Target From Word Beginnings Medium Palindrome by Adding Letters in Front Hard

Input

text="catnapdogcatnapcat", word="cat", anchor="dog", reach=4

Expected

[9]

Run checks the first 3 tests in your browser. Submit checks all 123 tests on the server, hidden ones included.