Мне понравилась идея недели борьбы с велосипедизмом, посему внесу свою лепту.

Один из частых вопросов, которые задают у нас в Блумберге на интервью в плане так называемого coding exercise (это когда надо на бумаге или на доске написать почти реальный кусок кода) - это поиск строки в подстроке. Это абсолютно жизненная задача.

Подавляющее число людей пишут первое, что приходит в голову - это два вложенных цикла, когда искомая строка последовательно “прикладывается” с каждой позиции исходной строки. Такой подход дает сложность O(M*N), и, очевидно, что в жизни он нереален, если строки более менее длинные. Хотя все при этом знают, что любой hex-вьювер спокойно ищет в огромных файлах за явно линейное время.

Итак, для эффективного поиска строки в подстроке есть алгоритм Кнута-Морриса-Пратта, который решает проблему не за O(N*M), а за O(N+M).

Построенный на префикс-функции, данный алгоритм является классичесим примером динамического программирования, когда результаты решения задачи малой размерности используются для решения задачи большей размерности.

P.S. Сразу скажу, у нас никто не просит по памяти писать КМП. И если человек после написания простого O(N^2) решения также скажет, что есть метод быстрее, и сможет описать его идею - этого вполне достаточно.