Текст хранится в виде последовательности литер. Необходимо отыскать в нем первое появление определенного «слова», которое можно определить как последовательность литер не длиннее самого текста.
текст: array[0..m-1] of character
слово: array[0..n-1] of character
i:=0; j:=0;
while (i < n) and (j < m – n) do
begin
i:=0;
while (i < n) and (слово[i]= текст[j+i]) do i:=i+1;
if i< n then j:= j+1;
end
Утверждения
Инвариант цикла
Обозначения:
Текст – D, длина текста - M
Слово – K, длина слова - N
[диапазоны для i и j]
[все подпоследовательности D до j-ой ¹ K
нет в D подпоследовательностей, равных K
[подпоследовательность D, начинающаяся с j, равна K до позиции i-1]
PETER_PIPER_PICKER_A_PECK
• P ICK
P ICK
Буква Расстояние
A 4
B 4
C 1
D 4