Pull to refresh

Comments 16

Зачем публиковать алгоритм, реализации которого уже сотни раз выкладывались в Интернет?
Вероятно интересует не сама реализация, а его разъяснение? Как если понимаешь математику/физику, любую формулу можно вывести самому
Интерес представляет именно вывод алгоритма и его разъяснение.
Надо заметить, что на практике обычно КМП в два раза медленнее своего наивного аналога. Дело в накладных расходах, константа в оценке сложности A*n велика, тогда как среднее время работы наивного алгоритма составляет всего 2*n, что легко показать и далеко от худшей оценки. Расскажите лучше про алгоритм Хорспулла: сам алгоритм простой, а вот вывод оценки сложности нетривиален.
На практике классические алгоритмы CS вообще редко применяются :) Это, конечно, провокационное утверждение, но у любой прикладной задачи, как правило, присутствует более простое, быстрое и менее универсальное решение, которое отлично подходит для нужд потребителя.

КМП относится к фундаментальным (вероятно, в отличие от Хорспулла) строковым алгоритмам, самым что ни на есть классическим. Со всеми вытекающими последствиями, например, для собеседований в некоторые компании :) Его `сила` состоит не в скорости исполнения, а в довольно простой реализации и доказательстве важной концепции: поиск подстрок может быть осуществлен за O(n) универсально, без использование `читов` вроде хэширования, предположений о размере алфавита, свойствах строки и т.д.

Если кому-то интересно копнуть поглубже — используемая в КМП префикс-функция может быть основой для более сложных строковых алгоритмов и подходов. Подробнее можно почитать, например, здесь.
Можете привести вывод среднего времени работы наивного алгоритма?
Статья неплохая, но позволю себе высказать пару замечаний. При определении префиксной функции используется формальное определение с небольшим пояснением, оба они читаются очень тяжело. Вот тут, к примеру, к этому добавлено текстовое описание того, что означают элементы посчитанной префиксной функции, это очень помогает понять её суть. Потому что об формальное определение (и о пояснение) можно мозг сломать. То же самое можно сказать и о дальнейшем описании уже сути алгоритма. По приведённой выше ссылке всё понятно, а здесь, увы, нет. Это касается и свойств префиксной функции, и собственно алгоритма.
«Проще говоря, это длина наиболее длинного начала строки, являющегося также и ее концом. „
Мне кажется, это интуитивно понятное определение. Плюс табличка служит примером.
В первом листинге переменные имеют «человеческие» имена. И код читается очень легко. Остальные читать тяжело.
Я понимаю, что у Кормена алгоритмы описаны аналогично, но зачем же вносить эту ненужную сложность?
Первый листинг читается сложнее, чем следующие — глаз вязнет в длинных именах, трудно увидеть логику.
А зачем в следующем фрагменте «i=1»? В этом есть смысл? Или просто невнимательность?
def prefix(s):
    v = [0]*len(s)
    i = 1
    for i in xrange(1,len(s)):
        k = v[i-1]
        ...
Откройте для себя возможность создавать else к циклам типа for в Python. Примитивный алгоритм можно записать без дополнительной переменной success:
index = -1
for i in xrange(len(haystack)-len(needle)+1):
    for j in xrange(len(needle)):
        if needle[j]<>haystack[i+j]:
            break
    else:
        index = i
        break
print index
Спасибо, удобная конструкция.
Only those users with full accounts are able to leave comments. Log in, please.