Есть массив M из нескольких тысяч строк, каждая длиной в среднем около 10-15 символов (сильно длинных нет, максимум около 30 символов). Берем какую-то другую строку s (длина тоже в среднем 10-15, максимум 30). Нужно найти элемент M, в котором достигается максимальная общая подстрока с s. Данную операцию повторить для массива S из ~100000 разных строк s.
Пробовал для каждой M искать максимальную с s подстроку по алгоритму
с википедии
- оно вроде работает, но слишком долго. Читал про другие алгоритмы- везде вроде пишут, что выгода достигается при длинных строках. У меня же строки короткие, просто задача много раз повторяется, вот и думаю, что напрямую эти алгоритмы нет смысла применять.Или можно объединить все строки из M в одну, уставив какой-то символ-разделитель между каждой строкой и уже тогда применять другой алгоритм? Имеет ли это смысл, если строки в S всё равно короткие и найти надо для каждой?
