Поиск подстроки в строке

Прямой поиск

Постановка задачи. Заданы две строки - 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; { Признак того, что подстрока найдена}