Search by template

A pattern $P$ and a text $T$ are given. Both consist of Latin letters (lowercase and uppercase). The pattern may additionally contain the characters ?, [, ], {, and }. You must find every position at which $P$ occurs in $T$.

Each position of the pattern $P$ is one of the following:

• a Latin letter (a–z, A–Z), which matches exactly that letter;
• the character ?, which matches any single letter;
• a group [...], listing the set of letters allowed at this position;
• a group {...}, listing the set of letters forbidden at this position (any other letter is allowed).

Letters may repeat inside a group, e.g. [asssa] or {kLLf}. Matching is case-sensitive.

For example, if the pattern is A?[bcCc]{De}, then the first letter of a match must be A, the second may be any Latin letter, the third must be b, c, or C, and the fourth may be any Latin letter except D and e.

The first line contains the number of test cases $n$. Each test case consists of two lines: the first line is the pattern $P$ (at most $100$ characters and at most $60$ positions), and the second line is the text $T$ (at most $10^6$ letters).

For each test case, print on its own line all positions in the text where the pattern matches, in ascending order (the first letter of $T$ is position $1$). Separate consecutive positions with a single space, with no leading or trailing space. If $P$ does not occur in $T$, print no match instead.