Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Упражнение № 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) Е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п ('Введите подстроку х.!); КеасИп (х) ; зеагсЬ(з,х); КеасИп Епс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зе с![з]:=к;






Дата добавления: 2014-11-10; просмотров: 208. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.007 сек.) русская версия | украинская версия