Строковые алгоритмы

1. Наивный алгоритм и его оценка в худшем случае. Z-функция Гасфилда и простейший линейный алгоритм; оценка числа сравнений.

2. Префикс-функция, алгоритм Морриса-Пратта, оценка 2n. Сильная префикс-функция, алгоритм Кнута-Морриса-Пратта. Дальнейшее усиление префикс-функции: переход к конечному автомату (сокращение числа сравнений до n за счет увеличения расходов памяти с m до mσ. Параллельный поиск набора образцов, автомат Ахо-Корасик, его построение за линейное время через функцию отказа.

3. Правила плохого символа и хорошего суффикса (в обычном и сильном варианте), алгоритм Бойера-Мура. Возможность обойтись сублинейным числом сравнений. Модификация Апостолико-Джианкарло, доказательство для нее верхней оценки в 2n сравнений.

4. Получисленные алгоритмы, область их применения. Алгоритм Shift-And. Приближенный поиск (с константной ошибкой по расстоянию Хэмминга).

5. Поиск с константной памятью (O(1) регистров). Лексикографический порядок. Поиск по автомаксимальному образцу. Вычисление максимального суффикса с константной памятью. Теорема о критическом разбиении. Алгоритм Крошмора-Перрена. Доказательство оценки в 2n сравнений. Real-time алгоритм Бреслауэра-Гросси-Миньози.

6. Джокеры и отношения совместимости. «Сложные» задачи поиска: совместимость вместо равенства. Быстрое преобразование Фурье. Алгоритмы над битовыми представлениями: σn log n для произвольного отношения совместимости и 2n log n log σ для джокеров. Численные представления: алгоритм Клиффорда-Клиффорда (3n log n). Трюк с разбиением текста для понижения log n до 2log m.
Часть 2. Известный текст (Задача индексирования текста).

7. Суффиксные структуры данных. Суффиксный бор и суффиксное дерево, задачи, решаемые с помощью суффиксного дерева. Поиск и подсчет вхождений.

8. Алгоритм Укконена.

9. Суффиксный массив и массив LCP. Построение с помощью суффиксного дерева. Решение задачи поиска и подсчета за время O(m+log n). Прямой линейный алгоритм построения суффиксного массива (на основе сэмпл-сортировки и метода разделяй-и-властвуй с одной подзадачей).

11. Преобразование Барроуза-Уилера. Сведение к сортировке суффиксов. Обратное преобразование через подсчет вхождений. FM-индекс. Решение задач поиска и подсчета.

1. 
   Д. Гасфилд, Строки, деревья и последовательности в алгоритмах. СПб: Невский диалект, 1997.
   
2. 
   M. Crochemore, W. Rytter. Jewels of Stringology. World Scientific, 2002.
   
3. 
   D. Breslauer, R. Grossi, F. Mignosi. Simple real-time constant-space string matching. Theoretical Computer Science 483 (2013), 2–9.
   
4. 
   P. Ferragina, G. Manzini, V. Makinen, G. Navarro. An Alphabet-Friendly FM-index. Proc. SPIRe 2004, 150-160.
   
5. 
   Ben Langmead. Introduction to the Burrows-Wheeler Transform and FM Index. Department of Computer Science, JHU (2013).
   
6. 
   P. Clifford, R. Clifford. Simple deterministic wildcard matching. Information Processing Letters 101 (2007) 53–54.
   
7. 
   S. Muthukrishnan, K. Palem. Non-standard stringology: algorithms and complexity. Proc. STOC 1994, ACM Press, New York (1994), 770–779.