Цитата(dapper91 @ 11.11.2014, 01:06  ) |
| работающий в худшем случае за N log(N). |
Что Вы разумеете под N в данном случае?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Нечеткий поиск подстроки за N log(N) |
| Автор: dapper91 11.11.2014, 00:06 |
| Доброго времени суток. Дана следующая задача: имеются две строки S1 и S2, длина S2 <= длины S1. Необходимо в строке S1 найти подстроку, наиболее близкую к S2 (с минимальным расстоянием Хэмминга). Пример: S1 = abcdef S2 = fdaf Ответ: cdef Подскажите пожалуйса алгоритм работающий в худшем случае за N log(N). Заренее спасибо) |
| Автор: Akina 11.11.2014, 08:49 | ||
Что Вы разумеете под N в данном случае? |
| Автор: dapper91 11.11.2014, 10:42 | ||
N - суммарная длина S1 и S2 (N = len(S1) + len(S2)) |
| Автор: Akina 11.11.2014, 11:15 |
| Хммм... в упор не понимаю зависимости от ЭТОГО значения. В данном случае сложность будет O(S1-S2)*O(Hamming(S2)) а расчёт расстояния Хэмминга емнип имеет квадратичную сложность. |
| Автор: dapper91 11.11.2014, 11:38 | ||
можешь пояснить почему? Это же просто пробежаться по строке и посчитать кол-во отличающихся позиций (O(N)) |
| Автор: Akina 11.11.2014, 11:52 | ||
Ну не говори ерунды, да? DiffPos('qwertyuio', 'wertyuiop') = 9 Hamming('qwertyuio', 'wertyuiop') = 2 |