In “Construct the Suffix Array of a String”, we introduced the suffix array. In this problem, we will let you use the suffix array to solve the Multiple Pattern Matching Problem (introduced in “Construct a Trie from a Collection of Patterns”).

Multiple Pattern Matching with the Suffix Array

Given: A string Text and a collection of strings Patterns.

Return: All starting positions in Text where a string from Patterns appears as a substring.

Sample Dataset

AATCGGGTTCAATCGGGGT
ATCG
GGGT

Sample Output

1 4 11 15

Extra Datasets

Click for debug datasets