Максим Крошемор , Тьерри Лекрок , Войцех Риттер - Алгоритмы обработки текста: 125 задач с решениями

Слова Сколема.......................................................................................................52
17. Слова Лэнгфорда. ..................................................................................................54
18. От слов Линдона к словам де Брёйна.................................................................56

Глава 3. Сопоставление с образцом............................................................59
19. Таблица границ.....................................................................................................60
20. Кратчайшие покрытия.........................................................................................62

6  Содержание
21. Короткие границы. ...............................................................................................64
22. Таблица префиксов...............................................................................................65
23. От таблицы границ к максимальному суффиксу.............................................67
24. Тест периодичности..............................................................................................69
25. Строгие границы...................................................................................................71
26. Задержка последовательного сопоставления строк........................................73
27. Разреженный автомат сопоставления...............................................................75
28. Сопоставление со строкой, эффективное с точки зрения числа
сравнений. ...................................................................................................................77
29. Таблица строгих границ слова Фибоначчи.......................................................79
30. Слова с подстановочными переменными. .......................................................81
31. Образцы, сохраняющие порядок........................................................................83
32. Параметрическое сопоставление.......................................................................85
33. Таблица хороших суффиксов..............................................................................87
34. Худший случай в алгоритме Бойера–Мура.......................................................89
35. Алгоритм Turbo-BM..............................................................................................91
36. Сопоставление с образцом при наличии универсального символа.............93
37. Циклическая эквивалентность............................................................................94
38. Простое вычисление максимального суффикса. .............................................96
39. Самомаксимальные слова...................................................................................98
40. Максимальный суффикс и его период.............................................................100
41. Критическая позиция в слове...........................................................................102
42. Периоды префиксов слов Линдона..................................................................105
43. Поиск слов Зимина.............................................................................................107
44. Поиск нерегулярных двумерных образцов.....................................................109

Глава 4. Эффективные структуры данных. ...........................................110
45. Списковый алгоритм для кратчайшего покрытия. .......................................111
46. Вычисление наибольших общих префиксов. .................................................112
47. От суффиксного массива к суффиксному дереву...........................................114
48. Линейное суффиксное trie-дерево...................................................................117
49. Троичное префиксное дерево поиска..............................................................120
50. Наибольший общий фактор двух слов.............................................................122
51. Автомат подпоследовательностей...................................................................124
52. Проверка однозначности декодирования.......................................................126
53. Таблица LPF. ........................................................................................................128
54. Сортировка суффиксов слов Туэ–Морса. ........................................................131
55. Простое построение суффиксного дерева. .....................................................133
56. Сравнение суффиксов слова Фибоначчи.........................................................135
57. Устранимость двоичных слов............................................................................137
58. Устранимость множества слов..........................................................................139
59. Минимальные уникальные факторы...............................................................141
60. Минимальные отсутствующие слова...............................................................143
61. Жадная суперстрока...........................................................................................146
62. Кратчайшая общая суперстрока коротких слов.............................................149
63. Подсчет факторов по длине. .............................................................................151
64. Подсчет факторов, покрывающих позицию...................................................153

Содержание  7

65. Наибольшие факторы с одинаковой четностью. ...........................................154
66. Установление свободы слова от квадратов с помощью словаря
базовых факторов.....................................................................................................155
67. Общие решения факторных уравнений..........................................................157
68. Поиск в бесконечном слове...............................................................................159
69. Совершенные слова............................................................................................161
70. Плотные двоичные --">