Поиск подстроки. Алгоритм Кнута–Морриса-Пратта

[lex_t]

Зачем публиковать алгоритм, реализации которого уже сотни раз выкладывались в Интернет?

[hell0w0rd]

Вероятно интересует не сама реализация, а его разъяснение? Как если понимаешь математику/физику, любую формулу можно вывести самому

[DarkGenius]

Интерес представляет именно вывод алгоритма и его разъяснение.

[excoder]

Надо заметить, что на практике обычно КМП в два раза медленнее своего наивного аналога. Дело в накладных расходах, константа в оценке сложности A*n велика, тогда как среднее время работы наивного алгоритма составляет всего 2*n, что легко показать и далеко от худшей оценки. Расскажите лучше про алгоритм Хорспулла: сам алгоритм простой, а вот вывод оценки сложности нетривиален.

[SkorKNURE]

На практике классические алгоритмы CS вообще редко применяются :) Это, конечно, провокационное утверждение, но у любой прикладной задачи, как правило, присутствует более простое, быстрое и менее универсальное решение, которое отлично подходит для нужд потребителя.

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

Если кому-то интересно копнуть поглубже — используемая в КМП префикс-функция может быть основой для более сложных строковых алгоритмов и подходов. Подробнее можно почитать, например, здесь.

[DarkGenius]

Можете привести вывод среднего времени работы наивного алгоритма?

[elw00d]

Статья неплохая, но позволю себе высказать пару замечаний. При определении префиксной функции используется формальное определение с небольшим пояснением, оба они читаются очень тяжело. Вот тут, к примеру, к этому добавлено текстовое описание того, что означают элементы посчитанной префиксной функции, это очень помогает понять её суть. Потому что об формальное определение (и о пояснение) можно мозг сломать. То же самое можно сказать и о дальнейшем описании уже сути алгоритма. По приведённой выше ссылке всё понятно, а здесь, увы, нет. Это касается и свойств префиксной функции, и собственно алгоритма.

[DarkGenius]

«Проще говоря, это длина наиболее длинного начала строки, являющегося также и ее концом. „
Мне кажется, это интуитивно понятное определение. Плюс табличка служит примером.

[return_true]

В первом листинге переменные имеют «человеческие» имена. И код читается очень легко. Остальные читать тяжело.
Я понимаю, что у Кормена алгоритмы описаны аналогично, но зачем же вносить эту ненужную сложность?

[Mrrl]

Первый листинг читается сложнее, чем следующие — глаз вязнет в длинных именах, трудно увидеть логику.

[return_true]

Разные подходы :)

[Mrrl]

Разные привычки :D

[iCune]

А зачем в следующем фрагменте «i=1»? В этом есть смысл? Или просто невнимательность?

def prefix(s):
    v = [0]*len(s)
    i = 1
    for i in xrange(1,len(s)):
        k = v[i-1]
        ...

[DarkGenius]

Это невнимательность. Убрал.

[grechnik]

Откройте для себя возможность создавать 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

[DarkGenius]

Спасибо, удобная конструкция.