CompF(pat, d);

Return flag;

}

S N

p M, 0<M<=N.

P(i,j) = A_k: 0 <= k < j: s_i+k = p_k

P(i,M) P(k,M) k<i:

Q(i) = A_k: 0 <= k < i: ~P(k,M)

Алгоритм 4:

i=-1;

Do

{ i++; j=0; // Q(i)

while ((j<M) && (s[i+j] == p[j])) j++;

// Q(i) && P(i,j) && ((j==M) || s[i+j]!= p[j]))

} while (j<M && i < N-M);

Алгоритм 5:

Hoola–Hoola girls like Hooligans.

Hooli gan

H ooligan

H ooligan

Hooli gan

H ooligan

...

Рассмотрим образец

J

J

J

i=0; j=0;

while(j<M && i<N)

{

while(j>=0 && s[i]!=p[j]) j=D;

i++; j++;

}

Текст: строка s[N].

Искомый образец: p[M].

Алфавит - множество символов a[A].

u - префикс w, если v: w=uv.

v - суффикс w, если u: w=uv.

z - граница w, если u и w: w=uz=zv, т.е. z - одновременно префикс и суффикс w.

Для X L(X)

L(abcab)=ab, L(cabcabc)=cabc

F(X) X

F(abcab)=2, F(cabcabc)=4

D F(). Далее F[k] будет означать F(p[1..K]).

X, L(X), L(L(X)), L(L(L(X))), …

length(X), F(X), F(F(X)), F(F(F(X)))… убывает и оканчивается нулем.

Алгоритм вычисления F[k].

Допустим, уже вычислили F[1],..., F[k-1]. На k -м шаге надо вычислить F[k].

Если p[k] = p[F[k-1]+1], то

F[k] = F[k-1]+ 1 (так как

p[1..F[k-1]] – суффикс p[1..k-1], и, следовательно,

p[1..F[k-1]+1] – суффикс p[1..k]).

Если же p[k] <> p[F(k-1)+1], то сравним

p[k] с p[F[F[k-1]]+1]. Если они равны, то

F[k] = F[F[k-1]]+1. И т.д. Получим

F[k] = F(q)[k-1]+1 или

F[k] = 0, если не существует префикс-суффикса для слова p[1..k].

void CompF(char* pat, int* d)

{

int i=0, len;

d[0]=-1;

for(i=1; pat[i]!=0; i++) {

len = d[i-1];

while (len>-1 && pat[len+1]!=pat[i])

len = d[len];

if(pat[len+1] == pat[i])

d[i]=len+1;

else d[i]=-1;

}

}

для образца ABDABD в массиве d окажутся значения: -1,-1,-1,0,1,2.

при несовпадении на i-ой позиции образец можно подвинуть по тексту на:

0: 0 - (-1) = 1 1: 1 – (-1) = 2 2: 2 – (-1) = 3

3: 3 – 0 = 3 4: 4 – 1 = 3 5: 5 – 2 = 3

///////////////////////////////////////////////////

int FindKMP (char* text, char* pat)

{

int i, j, lenT, lenP, d[100];

lenT = strlen(text); lenP = strlen(pat);

CompF(pat, d);

i=0; j=-1;

for (i=0; i < lenT; i++)

{

while (j>=0 && text[i]!=pat[j+1]) j = d[j];

if (text[i] == pat[j+1]) j++;

if (j+1==lenP) return 1;

}