Цитата(esperanto @ 21.6.2010, 08:34  ) |
| Если данные состоят из одной буквы одного вида. |
А откуда ,ты на перед это знаешь? Тебе придется проверить это. А проверка O(n) никак не O(1). O - число сравнений.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск подмассива в массиве |
| Автор: WERITAS 18.6.2010, 14:59 |
| Доброго времени суток. Требуется написать функцию, ищущую заданный образец в массиве байт. Читаю про методы поиска. В частности алгоритм Кнута-Мориса-Пратта и алгоритм Бойера-Мура, но никак не могу выбрать какой из них использовать. Может что-нибудь посоветуете |
| Автор: Akina 18.6.2010, 16:08 |
| http://algolist.manual.ru/search/esearch/index.php |
| Автор: Pavia 18.6.2010, 18:45 |
| Алгоритм грубой силы. Берем первый байт из масива который ищем и идем по массиву в котором ищем пока он не встретится потом проверяем весь массив до первого расхождения. Если не совпала дальше сдвигаем индекс на 1 и продолжаем поиск. Если этот массив имет вероятность распределения всех чисел 1/256 то в срднем будем иметь сложность примерно такую Т(n)+Т(n/256*log(m)) Для текста 1/A A- число букв алфовита Т(n)+Т(n/A*m) Что несколько многовато. Зато если представить массивы не как массивы байт а как массивы слов и будем сравнивать по словам получим вероятности совподения слов 1/65536 для текста 1/(A*A) тут уже вторым членом можно принебречь в среднем имеем Т(n) |
| Автор: esperanto 21.6.2010, 04:57 |
| предыдущее решение плохое |
| Автор: Pavia 21.6.2010, 05:12 |
| esperanto, предложи лучшее? Чем плохое? |
| Автор: esperanto 21.6.2010, 08:34 | ||
Если данные состоят из одной буквы одного вида. То проверям состоит ли подмассив из этой буквы. О(1). КМП достаточно хорош тут. |
| Автор: Pavia 21.6.2010, 19:25 |
| esperanto, Такое мало вероятно. По закону энтропии системам стремится к уменьшению оной. Отсюда большинство данных у нас сжаты. А так как обращение к массиву индексов не может выполняться за нулевое время, то это отъедает тики поэтому КМП не так уж хорош. |
| Автор: Pavia 21.6.2010, 20:06 | ||
А откуда ,ты на перед это знаешь? Тебе придется проверить это. А проверка O(n) никак не O(1). O - число сравнений. |
| Автор: newert 9.7.2010, 06:12 |
| Алгоритм грубой силы и правда здесь будет достаточно эффективен. Однако КМП можно смело использовать, не так уж и много времени отъест обращение к массиву |
| Автор: esperanto 9.7.2010, 09:23 | ||||
А с чего вы взяли что данные равноверятны. Они могут быть распределены по закону Вайбула, Паретта, Коши , да кого угодно. Упоминание закона энтропии тут с родни профанации. |
| Автор: Polesinskij 1.11.2013, 17:20 |
Модератор: Сообщение скрыто. |