Упражнение № 12. Поиск подстроки в строке

Пример 75. Заданы две строки 8 и х. Длина первой строки п, длина второй — т, причем 0< т< п. Требуется ответить на вопрос, является ли строка х подстрокой строки 8, при этом поиск подстроки должен обнаруживать первое вхождение х в з.

Решение. Самым простым методом поиска является метод прямого поиска. Рас­смотрим его на примере. Пусть 5 = «воротник», а х= «рот». Длина первой строки п = 8, длина второй — т = 3. В данном случае х является подстрокой 8, следователь­но, надо найти такое значение индекса /, что для любого значения индекса к (1„& „3) будет выполняться равенство $[/'+& ] = х[к].

Начальное значение / равно 0.

1- й шаг: / = 0, к= 1 — сравниваем з[1] и х[1]: «в» ф «р», значит, с первой пози­ции вхождения нет, надо увеличить на 1 значение 1.

2- й шаг: 1=1, к = 1 — сравниваем з[2] и х[1]: «о»*«р», снова надо перейти к следующему 1.

3- й шаг: 1 = 2, к — 1 — сравниваем я[3] и х[1]: «р» = «р», следовательно, воз­можно совпадение, надо увеличить к.

4- й шаг: 1=2, к= 2 — з[4] =х[2] («о» = «о») — снова надо увеличить к.

5- й шаг: 1=2, к= 3 — я[5]=х[3] («т» = «т») — полное совпадение! Далее поиск можно не продолжать, так как требовалось обнаружить лишь первое вхож­дение хв 5.

Таким образом, прямой поиск подстроки в строке сводится к последовательным сравнениям отдельных символов. Поиск продолжается до тех пор, пока не обнару­жится вхождение (факт вхождения будем хранить в логической переменной/) или пока не будет пройдена вся строка При этом можно закончить просмотр, когда / будет равно п — т, так как при следующих значениях / длина любого фрагмента строки ^ с позиции / меньше т.

Ргодгат Ехатр1е_7 5;

Уаг з, х: 5" Ьг1пд;

1, 3/П/Ш: 1п" Ьедег;

5: Воо1еап;

Ведхп

ДОг1" Ье1п (' введите з, х'); КеасИп (з); КеасИп (х);

п: =1епд1: Ь (з); ш: =1епд1: Ь (х); {определение длин строк}

х: =0;

1:: =Еа1зе; {признак того, что подстрока найдена} КереаЪ

(з< =ш) Ап< 3 (з[1 + Л=х[Л) ВоТпсЦ); II ^=т+1 ТЬеп ^: =Тгие Е1зе 1пс(1); 11п" Ы1 I Ог (л_> п-т);

II € ТЬеп ДОгИ: е1п(х, 'является подстрокой¹, з, ¹ с позиции - ', 1) Е1зе ДОгИ: е1п (х, ¹ не является подстрокой¹, з); Кеас11п; Епс1.

Этот алгоритм требует достаточно больших временных затрат, поскольку, ког­да п значительно больше т, число выполняемых сравнений — (п — т)т ~ пт.

Пример 76. Даны строка и подстрока. Составить программу, которая определяет вхождение подстроки в строку по алгоритму Бойера—Мура.

Решение. Поиск ведется от начала строки я, но с конца искомой подстроки х, для которой формируется таблица, размерность которой равна 256 (число всех возможных символов). Элементами таблицы являются расстояния от последнего символа искомой подстроки х до ее каждого символа. (Если в х встречаются одина­ковые символы, то в таблицу заносится расстояние до ближайшего из них.) Если символ в х не входит, то в соответствующую ячейку таблицы заносится т — длина подстроки х. Когда очередной символ подстроки не совпадает с очередным симво­лом строки для последнего из таблицы расстояний определяется соответствую­щее расстояние, после чего х сдвигается вправо на соответствующее число пози­ций. Тем самым ряд позиций пропускается, сокращая время поиска.

Ргодгат Ехатр1е_76; Уаг з, х: З-Ьгл-пд; 5< 3: Аггау [0.. 255] 05' 1пЪедег; РгосесЛиге зеагсЬ (з, х: 5Ъг1пд); Уаг 1,:), п, т: ХпЪедег; 5: Воо1еап; Ъ: СЬаг; Вед±п

п: =Ьепд1: Ь (з); т: =Ьепд1: Ь (х); {определение длин строки и подстроки; начальное заполнение массива расстояний} Еог 1: =0 То 255 Во з< 3[1]: =т;

Еог 1: =1 То т-1 Бо {заполнение массива расстояний} Вед±п

Ь: =х[1]; 5< 3[Ог< 3(Ъ) ]: =т-л_; Епс!;

1: =0; ^: =Еа1зе; {признак того, что подстрока найдена}

теЪИе (Кп-т+1) Ап< 3 (Ыо1: 5) Бо

Вед±п

3: =ш;

теЪИе ^> 0) Ап< 3 (з[1+Л=х[Л) Во □: =□ 15 ^=0 ТЪеп: 5: =Тгие {полное совпадение! } Е1зе 1: =1 + зсЦ0гс1(з [1 + Л) ]; Епс1;

15 5 ТЬеп ДОгИ: е1п(х, 'является подстрокой¹, з, 'с позиции', 1+1) Е1зе ДОгИ: е1п (' нет вхождения.'); Епс1;

Ведхп {Основная программа}

ДОгл_1: е1п (' Введите строку з.'); КеасИп (з); ДОгл_1: е1п ('Введите подстроку х.^! ); КеасИп (х); зеагсЬ(з, х); КеасИп Епс1.

Пример 77. Ниже представлена программа поиска подстроки в строке по алго­ритму Кнута, Мориса, Пратта. Изучите идею метода и работу алгоритма.

Ргодгат Ехатр1е_77; СопзЪ Шах=50; ММах=250; Туре М51: г1пд=51: г1пд [ММах]; Ы51: г: 1пд=51: г: 1пд [Шах]; Уаг з: МЗ^гл-пд; {строка} р: ^1: г: 1пд; {подстрока} ш: 1..Мшах; {длина строки} п: 1..№пах; {длина подстроки} с1: аггау [ 1..№пах] 1п1: едег; Ргосес1иге ТаЫе (х: Ы5-Ьгл_пд); {вычисление значений массива с! } Уаг 0..№пах; {текущий символ подстроки}

к: 0..№пах; {длина максимальной последовательности символов, совпадающих с началом подстроки} Ведхп

:: =1; к: =0; сЦ1]: =0; ШИе ^< п Бо Ведхп

тН1е (к> 0) апс! (р[^]< > р[к]) Бо к: =с! [к]; 1пс (з); 1пс(к);

р [ 3 ] =р [ к ] ТЬеп с! [з]: =с! [к] Е1зе с! [з]: =к;