Студопедия — Упражнение № 12. Поиск подстроки в строке
Студопедия Главная Случайная страница Обратная связь

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

Упражнение № 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; просмотров: 968. Нарушение авторских прав; Мы поможем в написании вашей работы!



Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Роль органов чувств в ориентировке слепых Процесс ориентации протекает на основе совместной, интегративной деятельности сохранных анализаторов, каждый из которых при определенных объективных условиях может выступать как ведущий...

Лечебно-охранительный режим, его элементы и значение.   Терапевтическое воздействие на пациента подразумевает не только использование всех видов лечения, но и применение лечебно-охранительного режима – соблюдение условий поведения, способствующих выздоровлению...

Тема: Кинематика поступательного и вращательного движения. 1. Твердое тело начинает вращаться вокруг оси Z с угловой скоростью, проекция которой изменяется со временем 1. Твердое тело начинает вращаться вокруг оси Z с угловой скоростью...

Гидравлический расчёт трубопроводов Пример 3.4. Вентиляционная труба d=0,1м (100 мм) имеет длину l=100 м. Определить давление, которое должен развивать вентилятор, если расход воздуха, подаваемый по трубе, . Давление на выходе . Местных сопротивлений по пути не имеется. Температура...

Огоньки» в основной период В основной период смены могут проводиться три вида «огоньков»: «огонек-анализ», тематический «огонек» и «конфликтный» огонек...

Упражнение Джеффа. Это список вопросов или утверждений, отвечая на которые участник может раскрыть свой внутренний мир перед другими участниками и узнать о других участниках больше...

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