eolymp
bolt
Try our new interface for solving problems
Məsələlər

Регулярные выражения Easy

Регулярные выражения Easy

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Регулярным выражением называется выражение, описывающее множество строк. В данной задаче регулярные выражения состоят из прописных латинских букв az и специальных символов '?', '*' и '+'. Каждая буква соответствует самой себе в описываемых строках. Специальный символ может стоять только после какой-то буквы, и означает количество повторений этой буквы:

Например, регулярному выражению "ab?c+" соответствуют строки "ac", "abc", "acc", "abcccc", и т. д.

В заданной строке найдите подстроку, удовлетворяющую заданному регулярному выражению. Если таких несколько, то выведите то, которое находится левее в исходной строке. Если и таких несколько, то выведите самую длинную из них.

Giriş verilənləri

Первая строка содержит T (1T100) — количество тестов. Затем следует T тестов. Первая строка каждого теста содержит строку S длины L (1L200). Следующая строка содержит целое число n (1n10) — количество регулярных выражений. Следующие n строк содержат n регулярных выражений длины R_i (1R_i2), по которым надо найти подстроки в S.

Для каждого регулярного выражения выведите соответствующую ему подстроку, или -1, если такой не существует.

Nümunə

Giriş verilənləri #1
1
aabbcc
5
ab
c+
ac
b*
a?
Çıxış verilənləri #1
ab
cc
-1

a