УДК 519.85(023) ББК 22.18 Деривативное электронное издание на основе печатного аналога: Алгоритмы обработки строк / С. М. Окулов. <...> Классические алгоритмы решения задач обработки строк . <...> Пятая глава посвящена достаточно значимойзадаче даннойпроблематики—приближенному поиску подстрок в тексте. <...> Проводя аналогию с языком программирования Паскаль, можно сказать, что для строки работают операции pred(i) и succ(i),где i—номер символа в строке, и справедливы равенства: i = succ(pred(i)) (за исключением самого левого символа) и i = pred(succ(i)) (за исключением самого правого символа). <...> Префикс строки S, заканчивающийся в позиции i,— это подстрока S[1.i]. <...> Суффикс строки S, начинающийся в позиции i, — это подстрока S[i.n]. <...> При этом возможны два исхода: произойдет несовпадение символов в какой-то позиции либо будет найдено вхождениеPвT(все символыPсравнены). <...> Строки Procedure Solve; {P, T – глобальные величины типа String} Var i,j:Integer; Begin For i:=1 To n-m+1 Do Begin j:=1; While (j<=m) And (P[j]=T[i+j-1]) Do j:=j+1; If j=m+1 Then WriteLn('найдено вхождение P в T, начиная с позиции ', i); End; End; Оценим время работы этого алгоритма в количестве операцийсравнения. <...> Последовательное применение предыдущей логики к каждойподстроке приводит к следующему алгоритму с временнойсложностью O(n3): Procedure MaxBorderArray(S:String); {Массив br - глобальный} Var i,n,t:Word; Begin n:=Length(S); br[1]:=0; For i:=2 To n Do br[i]:=MaxBorder(Copy(S,1,i)); {"Вырезаем" из S подстроку длины i, начиная с первого символа} End; Примеры В табл. <...> Формализованная запись алгоритма вычисления br для S может быть представлена так: Procedure MaxBorderArray(S:String); {Массив br - глобальный} Var i,n,t:Word; Begin <...>
Алгоритмы_обработки_строк_(2).pdf
УДК 519.85(023)
ББК 22.18
О-52
С е р и я о с н о в а н а в 2008 г.
Окулов С. М.
О-52 Алгоритмы обработки строк / С. М. Окулов.—
5-е изд., электрон.—М. : Лаборатория знаний, 2024.—
258 с.—(Развитие интеллекта школьников).—Систем.
требования: Adobe Reader XI ; экран 10".—Загл.
с титул. экрана.—Текст : электронный.
ISBN 978-5-93208-678-0
На материале задачи поиска подстроки в строке, решению
которой посвящены работы многих профессионалов
за последние 20–30 лет, показано, как построить занятия
по информатике, чтобы побудить школьника к творчеству,
развить у него вкус к решению исследовательских проблем.
Для школьников, преподавателей информатики, а также
для студентов, выбравших информатику в качестве основной
специальности. Книга может быть использована как в обычных
школах при проведении факультативных занятий, так
и в образовательных учреждениях с углубленным изучением
информатики и математики.
УДК 519.85(023)
ББК 22.18
Деривативное издание на основе печатного аналога: Алгоритмы
обработки строк / С. М. Окулов.—2-е изд.—
М. : БИНОМ. Лаборатория знаний, 2015.—255 с. : ил.—
(Развитие интеллекта школьников).
ISBN 978-5-9963-1931-2.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации
ISBN 978-5-93208-678-0
© Лаборатория знаний, 2015
Стр.3
Оглавление
Предисловие ........................................... 5
Глава 1. Строки ........................................... 9
1.1. Основные понятия .............................. 9
1.2. Методы предварительного анализа строк ......... 13
Глава 2. Классические алгоритмы решения задач
обработки строк ................................ 28
2.1. Алгоритм Д. Кнута –Дж. Морриса – В. Пратта .... 28
2.2. Алгоритм Р. Бойера –Дж.Мура ................. 36
2.3. Алгоритм Р. Карпа –М. Рабина.................. 52
2.4. Алгоритм Shift-And............................ 57
2.5. Использование элементов теории автоматов
в решении задач обработки строк ................ 73
2.6. Алгоритм М. Крочемора ........................ 81
2.7. Алгоритм М.Мейна – Р. Лоренца ................ 88
Глава 3. Деревья суффиксов............................ 103
3.1. Основные понятия. Простые алгоритмы
построения дерева суффиксов .................. 103
3.2. Алгоритм Э. Укконена ........................ 118
3.3. Алгоритм Е. Мак-Крейга ...................... 127
3.4. Суффиксные массивы ......................... 136
3.5. Алгоритм А. Ахо –М. Корасик ................. 147
Глава 4. Вычисление расстояния между строками . ..... 155
4.1. Основнойалгоритм ........................... 155
4.2. Алгоритм Э. Укконена –Ю.Майерса ............ 165
4.3. Задача о наибольшейобщей
подпоследовательности двух строк ............. 174
Стр.4
4
Оглавление
Глава 5. Алгоритмы приближенного поиска подстрок . . 198
5.1. Простойалгоритм ............................ 198
5.2. Алгоритм С. Ву–Ю. Менбера .................. 201
5.3. Задача о k-несовпадениях...................... 205
5.4. АлгоритмЮ.Майерса......................... 215
Вместо заключения ................................... 225
Приложения ......................................... 234
Стр.5