seriych
31-03-2014, 21:40
Я так понял продвинутые алгоритмы дают преимущество на длинных строках, у меня же строки короткие. Я программирую от случая к случаю, поэтому реализация любого алгоритма затянется и могу потратить впустую кучу времени на реализацию неподходящего. Может кто сталкивался и сразу подскажет, какой оптимальнее в моем случае.
Есть массив M из нескольких тысяч строк, каждая длиной в среднем около 10-15 символов (сильно длинных нет, максимум около 30 символов). Берем какую-то другую строку s (длина тоже в среднем 10-15, максимум 30). Нужно найти элемент M[i], в котором достигается максимальная общая подстрока с s. Данную операцию повторить для массива S из ~100000 разных строк s.
Пробовал для каждой M[i] искать максимальную с s подстроку по алгоритму с википедии (http://ru.wikipedia.org/wiki/%CD%E0%E8%E1%EE%EB%FC%F8%E0%FF_%EE%E1%F9%E0%FF_%EF%EE%E4%F1%F2%F0%EE%EA%E0) - оно вроде работает, но слишком долго. Читал про другие алгоритмы- везде вроде пишут, что выгода достигается при длинных строках. У меня же строки короткие, просто задача много раз повторяется, вот и думаю, что напрямую эти алгоритмы нет смысла применять.
Или можно объединить все строки из M в одну, уставив какой-то символ-разделитель между каждой строкой и уже тогда применять другой алгоритм? Имеет ли это смысл, если строки в S всё равно короткие и найти надо для каждой?
Есть массив M из нескольких тысяч строк, каждая длиной в среднем около 10-15 символов (сильно длинных нет, максимум около 30 символов). Берем какую-то другую строку s (длина тоже в среднем 10-15, максимум 30). Нужно найти элемент M[i], в котором достигается максимальная общая подстрока с s. Данную операцию повторить для массива S из ~100000 разных строк s.
Пробовал для каждой M[i] искать максимальную с s подстроку по алгоритму с википедии (http://ru.wikipedia.org/wiki/%CD%E0%E8%E1%EE%EB%FC%F8%E0%FF_%EE%E1%F9%E0%FF_%EF%EE%E4%F1%F2%F0%EE%EA%E0) - оно вроде работает, но слишком долго. Читал про другие алгоритмы- везде вроде пишут, что выгода достигается при длинных строках. У меня же строки короткие, просто задача много раз повторяется, вот и думаю, что напрямую эти алгоритмы нет смысла применять.
Или можно объединить все строки из M в одну, уставив какой-то символ-разделитель между каждой строкой и уже тогда применять другой алгоритм? Имеет ли это смысл, если строки в S всё равно короткие и найти надо для каждой?