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

Поиск похожих строк (LCS + Расстояние Левенштейна)

Поиск похожих строк (LCS + Расстояние Левенштейна)

Дан набор строк ${S}_{1}, {S}_{2}, ..., {S}_{n}$ (в общем случае разной длины), состоящих из строчных букв латинского алфавита. Дана строка $T$ (запрос пользователя), также состоящая из строчных букв латинского алфавита. Каждая строка ${S}_{i}$ содержит не более 5 слов. Строка $T$ также содержит не более 5 слов. Слова отделены пробелами. Необходимо найти \textbf{«наиболее похожую»} на запрос пользователя строку из набора. Будем учитывать, что: \begin{enumerate} \item Пользователь мог ввести только часть (подпоследовательность) строки, которую хотел найти в наборе. \item Пользователь мог допустить опечатки: пропуск букв, написание лишних букв, замена букв на другие. \item Пользователь мог поменять слова местами. \end{enumerate} \InputFile Число $n$, ($n \le 200$). Затем следует строка $T$, ($ 3 \le |T| \le 15$). Далее следуют строки ${S}_{1}, {S}_{2}, ..., {S}_{n}$, ($ 3 \le |{S}_{i}| \le 15$). \OutputFile Порядковый номер $i$ строки из набора ${S}_{1}, {S}_{2}, ..., {S}_{n}$, \textbf{«наиболее похожей»} на $T$. \Example \begin{example} \exmp{8 kayu u eomneky dgn f hsobhelzjk mvh ei tq z v fo nzm pm w jpkymliu oioupsiw}{7} \end{example}
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Müəllif Александр Биданец