Задачи
Поиск по шаблону
Поиск по шаблону
Имеются шаблон \textbf{P} и текст \textbf{T}, состоящие из букв латинского алфавита (верхнего или нижнего регистра). Шаблон может содержать также знаки вопроса ('\textbf{?}'), квадратные и фигурные скобки, смысл которых описан ниже. Необходимо найти все вхождения шаблона \textbf{P} в текст \textbf{T}.
Каждая позиция в шаблоне \textbf{P} может быть занята:
\begin{itemize}
\item буквой латинского алфавита ('\textbf{a}' - '\textbf{z}', '\textbf{A}' - '\textbf{Z}')
\item символом '\textbf{?}', на месте которого может находиться любая буква
\item квадратными скобками \textbf{\[...\]}, где на месте трех точек находится набор букв, которые могут находиться в текущей позиции
\item фигурными скобками \textbf{\{...\}}, где на месте трех точек находится набор букв, которые не могут находиться в текущей позиции
\item буквы в скобках могут повторяться, как например \[\textbf{asssa}\] или \{\textbf{kLLf}\}
\end{itemize}
Например, если шаблон \textbf{P} задается в виде \textbf{A?\[bcC\]\{De\}}, то первой буквой слова должна быть '\textbf{A}', второй может быть любая буква, третьей - буква \textbf{b}, \textbf{c} или \textbf{C}, а четвертой любая буква кроме \textbf{D} или \textbf{e}.
\InputFile
Первая строка содержит количество тестов \textbf{n}. Каждый тест состоит из двух строк. Первая строка содержит шаблон \textbf{P}, содержащий не более\textbf{ 100} символов и \textbf{60} позиций. Вторая строка содержит текст, состоящий из не более чем \textbf{10^6} букв.
\OutputFile
Для каждого теста в отдельной строке вывести все позиции текста, с которых может начинаться шаблон, в возрастающем порядке (первый символ текста \textbf{T} находится в позиции '\textbf{1}'). Если шаблон \textbf{P} не встречается в тексте \textbf{T}, то следует вывести сообщение "\textbf{no match}". Между выводимыми позициями должен находиться один пробел, а в начале или в конце каждой строки должны отсутствовать лишние пробелы.
Входные данные #1
3 A?[bcC]{De} yAqCpsApbeAocqq ???[QWERTY] aSdFrQererRTY {eRT}? eRTeRTq
Выходные данные #1
2 11 3 8 9 10 no match