Выбираем интересующие темы. Строки и всё, что с ними связано.

Продолжаем разговор.

Одной из тем, которую я касался за эти годы реже всего - это строковые алгоритмы. Кроме поиска палиндромов, КМП ничего не писал. Думаю пришло время закрывать этот важный пробел. Тем более часто видел задачи, которые судя по отзывам решаются суффиксными структурами.

Начну с первых глав в ifmo wiki - Основные определения. Простые комбинаторные свойства слов.

Что касается непосредственно алгоритмов поиска подстроки в строке:

1. Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа ( ifmo wiki , e-maxx ) + Поиск наибольшей общей подстроки двух строк с использованием хеширования ( ifmo wiki ). Приоритет - средний.
2. Префикс-функция+ Алгоритм Кнута-Морриса-Пратта ( ifmo wiki 1, 2, e-maxx ). Приоритет - высокий.
3. Z-функция ( ifmo wiki , e-maxx). Приоритет - высокий
4. Автомат для поиска образца в тексте ( ifmo wiki , e-maxx ). Приоритет - средний
5. Нахождение всех подпалиндромов за O (N) (e-maxx). Приоритет - низкий.
6. Бор + Алгоритм Ахо-Корасик ( ifmo wiki 1, 2 , e-maxx ). Приоритет - высокий

Суффиксное дерево.Алгоритм Укконена (ifmo wiki , e-maxx ). Приоритет - высокий.
Суффиксный массив (ifmo wiki , e-maxx ). Приоритет - высокий.

После появления поста на Codeforces о примере построения теста, который ломает любое хэш-решение, которое использует стандартное переполнение 64 разрядного типа стоит особо внимательно относиться к хэш решениям. Статья на e-maxx про них специально не добавлена, т.к. собственно способ хэширования, который там описывается как раз и был взломан. Будем ждать фикса.
Вообще пропихивание хэшей это скользкий путь, может повезти, а может - нет. Поэтому изучение суффиксных структур кажется весьма актуальным.
А вообще про хэширование много написано как в Кормене, так и в ifmo wiki.