Киберфак – бесплатно скачать презентации PowerPoint, лекции, рефераты, шпоры, курсовые cyberfac logo
cyberfac.ru
На главную | Регистрация | Вход
  Статьи  
Главная » Статьи » Информатика » Алгоритмизация и программирование

Поиск подстроки в строке. Прямой поиск

Полезная статья? Пожалуйста, поставьте "+"
Алгоритмизация и программирование - Содержание
Постановка задачи.    Заданы две строки - s и x. Длина первой строки - n, длина второй - m, причем  0 ≤ m ≤ n. Требуется определить, является ли строка x подстройкой строки s, при этом требуется обнаружить первое вхождение x  в  s.
Самым простым методом поиска является метод прямого поиска. Рассмотрим его на примере. Пусть s = ‘воротник’, а x = ‘рот’. Длина первой строки n = 8, длина второй - m = 3. В данном случае строка x короче s, следовательно, нужно найти такое решение индекса i, что для любого значения индекса к - 1 ≤ k ≤ 3 будет выполняться равенство s [ i + k ] = x [ k ].
Начальное значение i равно 0.

1 - й  шаг
i = 0, k = 1 - сравниваем s [ 1 ] и x [ 1 ]: ‘в’ ≠ ‘p’, значит, с первой позиции вхождения нет, нужно увеличить на 1 значение i.

2-й шаг
i = 1, k = 1 - сравниваем s [ 2 ] и x [ 1 ]: ‘o’ ≠ ‘p’, снова надо перейти к следующему i.

3 -й шаг
i = 2, k = 1 - сравниваем s [ 3 ]  и x [ 1 ]: ‘p’ = ‘p’, следовательно, возможно совпадение, нужно увеличить k.

4-й шаг
i = 2, k = 2 - s [ 4 ] = x [ 2 ]:  ‘o’ = ‘o’  - снова надо увеличить k.

5-й шаг
i = 2, k = 3 - s [ 5 ] = x [ 3 ]:  ‘т’ = ‘т’  - полное совпадение! Далее поиск можно не продолжать, так как требовалось обнаружить лишь первое вхождение x  в  s.
Таким образом, прямой поиск подстроки в строке сводится к последовательным сравнениям отдельных символов. Поиск продолжается до тех пор, пока не обнаружится вхождение или пока не будет пройдена вся строка s. При этом можно  закончить просмотр, когда i будет равно  n-m, так как при следующих значениях i длина любого фрагмента строки s с позиции i меньше m.
Ниже приведена программа, реализующая метод прямого поиска подстроки.

Program n10;var s,x: string;
i,j,n,m: integer;
f: boolean;
begin
writeln('Введите строку s: ');
readln(s);
writeln('Введите строку x: ');
readln(x);
n:=length(s); m:=length(x);{ Определение длин строк }
i:=0;
f:=False;                  { Признак того, что подстрока найдена}
repeat
j:=1;
while (j<=m) and (s[i+j] =x[j]) do inc(j);
if j=m+1 then f:=true else inc(i);
until f or (i>n-m);
if f then writeln(x,' является подстрокой ',s,' с позиции - ',i+1)
Else writeln(x, ' не является подстрокой ',s);
readln;
end.

Этот алгоритм требует достаточно больших временных затрат, поскольку, когда  n значительно больше m, количество выполняемых сравнений –
( n-m )*m ≈ n*m.
Категория: Алгоритмизация и программирование | Добавил: Ni-Cd (10 Декабря 2011)
Просмотров: 1917 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

В нашем каталоге файлов можно найти много полезной информации. Также советуем заглянуть в каталог статей: в нем есть полезные статьи по темам: Экономика предприятия, Общая экономика, Финансы и Кредит, также Словарь терминов по экономике, Маркетинг, Бухучет и Мировая экономика
Также есть полезная страница Факультеты МИФИ, которая расскажет о том, какие есть в МИФИ факультеты.
Меню
 

Навигация
Высокоуровневые методы информатики и программирования [28]
Информатика и программирование [34]
Информационные системы в экономике [36]
Языки программирования и методы трансляции [15]
Алгоритмизация и программирование [61]
 

Поиск
 

Онлайн
Онлайн всего: 1
Гостей: 1
Пользователей: 0
 

Статистика


Рейтинг@Mail.ru

 


2007 - 2024 © Ni-Cd. All Rights Reserved