Пошук за шаблоном#2562
Шаблон P і текст T складаються з літер латинського алфавіту (великі або малі). Шаблон також може містити знак питання ('?'), квадратні та фігурні дужки, як пояснено нижче. Знайдіть усі входження шаблону P у текст T.
Кожна позиція у шаблоні P може бути зайнята:
літерою латинського алфавіту ('a' - 'z', 'A' - 'Z')
символом '?', що означає будь-яку літеру
квадратними дужками [...], у яких перераховані дозволені в цій позиції літери
фігурними дужками {...}, у яких перераховані заборонені в цій позиції літери
літери в дужках можуть повторюватись, наприклад [asssa] чи {kLLf}
Наприклад, якщо шаблон P дорівнює A?[bcC]{De}, то перша літера повинна бути 'A', друга — будь-яка літера, третя — b, c або C, а четверта — будь-яка літера, крім D чи e.
У першому рядку задано кількість тестів . Кожен тест складається з двох рядків. У першому рядку задано шаблон P, який містить не більше символів і позицій. У другому рядку задано текст, що містить не більше 10^6 літер.
Для кожного тесту виведіть в окремому рядку всі позиції початку у тексті, в яких співпадає шаблон, у зростаючому порядку (перша літера тексту T має позицію ). Якщо шаблон P не знайдено у тексті T, виведіть "no match". Між кожною надрукованою позицією має бути один пробіл, без зайвих пробілів на початку або в кінці кожного рядка.
Приклад 1