Постановка задачи. Заданы две строки - 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.
