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}