Комментарии 16
Зачем публиковать алгоритм, реализации которого уже сотни раз выкладывались в Интернет?
Надо заметить, что на практике обычно КМП в два раза медленнее своего наивного аналога. Дело в накладных расходах, константа в оценке сложности A*n велика, тогда как среднее время работы наивного алгоритма составляет всего 2*n, что легко показать и далеко от худшей оценки. Расскажите лучше про алгоритм Хорспулла: сам алгоритм простой, а вот вывод оценки сложности нетривиален.
На практике классические алгоритмы CS вообще редко применяются :) Это, конечно, провокационное утверждение, но у любой прикладной задачи, как правило, присутствует более простое, быстрое и менее универсальное решение, которое отлично подходит для нужд потребителя.
КМП относится к фундаментальным (вероятно, в отличие от Хорспулла) строковым алгоритмам, самым что ни на есть классическим. Со всеми вытекающими последствиями, например, для собеседований в некоторые компании :) Его `сила` состоит не в скорости исполнения, а в довольно простой реализации и доказательстве важной концепции: поиск подстрок может быть осуществлен за O(n) универсально, без использование `читов` вроде хэширования, предположений о размере алфавита, свойствах строки и т.д.
Если кому-то интересно копнуть поглубже — используемая в КМП префикс-функция может быть основой для более сложных строковых алгоритмов и подходов. Подробнее можно почитать, например, здесь.
КМП относится к фундаментальным (вероятно, в отличие от Хорспулла) строковым алгоритмам, самым что ни на есть классическим. Со всеми вытекающими последствиями, например, для собеседований в некоторые компании :) Его `сила` состоит не в скорости исполнения, а в довольно простой реализации и доказательстве важной концепции: поиск подстрок может быть осуществлен за 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
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск подстроки. Алгоритм Кнута–Морриса-Пратта