Задачи
Общая подстрока (Easy)
Общая подстрока (Easy)
Заданы две строки, состоящие из \textbf{0} и \textbf{1}. Рассмотрим все строки, которые являются подстроками обеих данных строк. Найдите среди них \textbf{k}-ую в лексикографическом порядке.
Строка \textbf{S} меньше строки \textbf{T} в лексикографическом порядке, если выполняется одно из двух условий:
\begin{itemize}
\item \textbf{S} является префиксом \textbf{T};
\item существует \textbf{i}, не превышающее длин строк \textbf{S} и \textbf{T}, такое, что для \textbf{j} < \textbf{i} выполняется \textbf{S\[j\] = T\[j\]} и \textbf{S\[i\]} < \textbf{T\[i\]}.
\end{itemize}
\InputFile
Первые две строки входного файла содержат заданные строки, длиной не более \textbf{100} символов каждая. Третья строка содержит целое положительное число \textbf{k}, не превышающее количества общих подстрок двух заданных строк.
\OutputFile
Выведите в выходной файл \textbf{k}-ую в лексикографическом порядке общую подстроку заданных строк.
Входные данные #1
0100 0010 3
Выходные данные #1
01