Алгоритм Кнута-Морриса-Пратта (КМП)

См. видеозаписи лекций ЛКШ.2008.B', раздел "Алгоритмы на строках".
Теория на e-maxx
Теория на хабре
Можете в интернете поискать еще.
Помимо собственно поиска подстроки в строке, префикс-функция сама по себе также нередко имеет другие полезные применения. Задачи на это ниже тоже есть.
Какие-то из задач ниже, наверное, были ранее в задачах на хеши. Решите их повторно с использованием КМП.