 Максимальное совпадение двух строк |
  |
| Unconnected |
 8.10.2012 3:22
Сообщение
#1
|
 mea culpa  Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация:  24   |
Дано 10 строк из латинских lowcase символов, каждая строка до 10 000 символов. Нужно найти максимальную общую подстроку, за секунду.
Есть алгоритм, работающий для двух строк за O(mn). Думал найти все общие подстроки для двух строк, а потом искать (за O(n)) каждую подстроку в других строках, дактилоскопическим методом, или КМП.. но это всё равно как-то долго. Потом нашел в сети алгоритм, работающий за m*n*log(m) (m длины, n кол-во строк), и он на 10 строках по 10к символов работает 5 сек.. -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
   |
 
|
| TarasBer |
8.10.2012 9:46
Сообщение
#2
|
 Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
-------------------- |
|
|
|
| Анон |
14.01.2013 22:53
Сообщение
#3
|
|
Гость |
Цитата(Unconnected @ 8.10.2012 3:22)  Дано 10 строк из латинских lowcase символов, каждая строка до 10 000 символов. Нужно найти максимальную общую подстроку, за секунду. Есть алгоритм, работающий для двух строк за O(mn). Думал найти все общие подстроки для двух строк, а потом искать (за O(n)) каждую подстроку в других строках, дактилоскопическим методом, или КМП.. но это всё равно как-то долго. Потом нашел в сети алгоритм, работающий за m*n*log(m) (m длины, n кол-во строк), и он на 10 строках по 10к символов работает 5 сек.. А что это за алгоритм такой? На 100 строках сработает? |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 3.11.2024 15:58 |