Start

2019-04-01 13:00 UTC

Kattis Set 11

End

2019-04-08 09:29 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -225 days 22:38:14

Time elapsed

164:29:59

Time remaining

0:00:00

Problem I
String Multimatching

Input

The input consists of at most ten test cases. Each test case begins with an integer $n$ on a line of its own, indicating the number of patterns. Then follow $n$ lines, each containing a non-empty pattern. The total length of all patterns in a test case is no more than $100\, 000$. Then comes a line containing a non-empty text (of length at most $200\, 000$). Input is terminated by end-of-file.

Output

For each test case, output $n$ lines, where the $i$’th line contains the positions of all the occurrences of the $i$’th pattern in text, from first to last, separated by a single space.

Sample Input 1 Sample Output 1
2
p
pup
Popup
2
You
peek a boo
you speek a bootiful language
4
anas
ana
an
a
bananananaspaj
2 4
2

5
7
1 3 5 7
1 3 5 7
1 3 5 7 9 12