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

Дан набор строк $S_1,S_2,...,S_n$ (в общем случае разной длины), состоящих из строчных букв латинского алфавита.

Дана строка $T$ (запрос пользователя), также состоящая из строчных букв латинского алфавита.

Каждая строка $S_i$ содержит не более 5 слов.

Строка $T$ также содержит не более 5 слов.

Слова отделены пробелами.

Необходимо найти «наиболее похожую» на запрос пользователя строку из набора.

Будем учитывать, что:

1. Пользователь мог ввести только часть (подпоследовательность) строки, которую хотел найти в наборе.

2. Пользователь мог допустить опечатки: пропуск букв, написание лишних букв, замена букв на другие.

3. Пользователь мог поменять слова местами.

Giriş verilənləri

Число $n$, ($n\le 200$).

Затем следует строка $T$, ($3\le |T|\le 15$).

Далее следуют строки $S_1,S_2,...,S_n$, ($3\le |S_i|\le 15$).

Çıxış verilənləri

Порядковый номер $i$ строки из набора $S_1,S_2,...,S_n$, «наиболее похожей» на $T$.

Nümunələr

8
kayu
u eomneky
dgn
f hsobhelzjk
mvh
ei tq
z v fo nzm
pm w jpkymliu
oioupsiw

7