7. Поиск подстроки. Алгоритм Кнута-Морриса- Пратта.

Поиск подстроки.

Вход: Строки T длины n и P длины m.

Вопрос: содержит ли T подстроку равную P?

P встречается в T со сдвигом s, если T[1+s,…s+m]=P[1,…s]. В таком случае s -допустимый сдвиг,если T[1+s,…s+m]≠P[1,…s], то s – недопустимый сдвиг.

for ( s = 0; s<=n-m;s++)

{ b= true;

for(i= s; i<=s+m;i++)

if(T[s+i]!=P[i])

{ b=false;

break;}

if(b)

cout<<”Yes”;}

Трудоемкость O((n-m)m). Недостаток алгоритма: для сдвигов s’>s он не исп. инфу полученную при обработке сдвига s.

Алгоритм Кнута-…

Опр. Конечным автоматом называется четверка (Q,q₀,), где Q – конечное мн-во состояний, q₀ – начальное состояние, - конечный входной алфавит,-ф-ия из Qxв Qx,назыв ф-ией перехода автоматов.

Опр. Конечным автоматом называется пятерка (Q,q₀, А,), где Q – конечное мн-во состояний, q₀ – начальное состояние, А€Q – конечное мн-во допускающих значений, - конечный входной алфавит,-ф-ия из Qxв Q,назыв ф-ией перехода автоматов.

T = a b b a b a b a b a b c b a

Автомат для сравнения с образцом Р = a b a b c b

temp;

fail[1] = 0;

for(int i=2; i<=m; i++)

{

temp = fail[i-1];

while(temp>0 && (P[temp]!=P[i-1]))

temp = fail[temp];

fail[i] = temp+1;

}

Трудоемкость O(m)

Tpos=1, Ppos=1;

while((Tpos<=n) && (Ppos<=m))

{

if(Ppos == 1 || (T[Tpos] == P[Ppos]))

{ Tpos++; Ppos++;}

else{Ppos = fail[Ppos];}

}

if(Ppos >= m) {return Tpos-m+1;}

else {return 0;}

Трудоемкость O(n)

Теорема. Алгоритм Кнута-Моррриса-Пратта выполняет порядка O(n+m) операций при поиске образца длины m в строке длины n.