Доброго времени суток. Требуется написать функцию, ищущую заданный образец в массиве байт. Читаю про методы поиска. В частности алгоритм Кнута-Мориса-Пратта и алгоритм Бойера-Мура, но никак не могу выбрать какой из них использовать. Может что-нибудь посоветуете 

http://algolist.manual.ru/search/esearch/index.php

Алгоритм грубой силы. Берем первый байт из масива который ищем и идем по массиву в котором ищем пока он не встретится  потом проверяем весь массив до первого расхождения. Если не совпала дальше сдвигаем индекс на 1 и продолжаем поиск.

Если этот массив имет вероятность распределения всех чисел 1/256 то в срднем будем иметь сложность примерно такую Т(n)+Т(n/256*log(m))
Для текста 1/A A- число букв алфовита Т(n)+Т(n/A*m) 
Что несколько многовато. Зато если представить массивы не как массивы байт а как массивы слов и будем сравнивать по словам 
получим вероятности совподения  слов 1/65536 для текста 1/(A*A)  тут уже вторым членом можно принебречь в среднем имеем Т(n)

предыдущее решение плохое

esperanto, 
предложи лучшее? Чем плохое?

Если данные состоят из одной буквы одного вида.

То проверям состоит ли подмассив из этой буквы.


О(1).

КМП достаточно хорош тут.

esperanto, 
Такое мало вероятно. По закону энтропии системам стремится к уменьшению оной.  Отсюда большинство данных у нас сжаты.
А так как обращение к массиву индексов не может выполняться за нулевое время, то это отъедает тики поэтому КМП не так уж хорош.

А откуда ,ты на перед это знаешь? Тебе придется проверить это. А проверка O(n) никак не O(1). O - число сравнений.

Это сообщение отредактировал(а) Pavia - 21.6.2010, 20:13

Алгоритм грубой силы и правда здесь будет достаточно эффективен.
Однако КМП можно смело использовать, не так уж и много времени отъест обращение к массиву

А с чего вы взяли что данные равноверятны. 

Они могут быть распределены по закону Вайбула, Паретта, Коши , да кого угодно.

Упоминание закона энтропии тут с родни профанации.