Məsələlər
Регулярные выражения Hard
Регулярные выражения Hard
Регулярным выражением называется выражение, описывающее множество строк. В данной задаче регулярные выражения состоят из прописных латинских букв \textbf{a}--\textbf{z} и специальных символов '\textbf{?}', '\textbf{*}' и '\textbf{+}'. Каждая буква соответствует самой себе в описываемых строках. Специальный символ может стоять только после какой-то буквы, и означает количество повторений этой буквы:
Например, регулярному выражению "\textbf{ab?c+}" соответствуют строки "\textbf{ac}", "\textbf{abc}", "\textbf{acc}", "\textbf{abcccc}", и т. д.
В заданной строке найдите подстроку, удовлетворяющую заданному регулярному выражению. Если таких несколько, то выведите то, которое находится левее в исходной строке. Если и таких несколько, то выведите самую длинную из них.
\InputFile
Первая строка содержит \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}) --- количество тестов. Затем следует \textbf{T} тестов. Первая строка каждого теста содержит строку \textbf{S} длины \textbf{L} (\textbf{1} ≤ \textbf{L} ≤ \textbf{200}). Следующая строка содержит целое число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10}) --- количество регулярных выражений. Следующие \textbf{n} строк содержат \textbf{n} регулярных выражений длины \textbf{R_i} (\textbf{1} ≤ \textbf{R_i} ≤ \textbf{100}), по которым надо найти подстроки в \textbf{S}.
\InputFile
Для каждого регулярного выражения выведите соответствующую ему подстроку, или \textbf{-1}, если такой не существует.
Giriş verilənləri #1
1 aabbcc 5 b*c a?b+c+ ab?c b?c? a?b?c?
Çıxış verilənləri #1
bbc abbcc -1 a