Поиск слова в тексте

Текст хранится в виде последовательности литер. Необходимо отыскать в нем первое появление определенного «слова», которое можно определить как последовательность литер не длиннее самого текста.

текст: 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