Return 0;

}

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

int FindKMP (char* text, char* pat)

{

int i, j, lenT, lenP, flag=0;

int d[100];

lenT = strlen(text);

lenP = strlen(pat);

j = 0;

CompF(pat, d);

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

printf(" %d ",d[i]);

printf("\n");

i = 0;j=-1;

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

{

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

{

j = d[j];

printf("%s (%d)\n", &text[i-j], j);

}

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

if (j+1==lenP)

{

printf ("Ok!\n"); return 1;

}

}

Return 0;

}

#include <stdlib.h>

#include <string.h>

#include <memory.h>

#include <conio.h>

int FindKMP(char* text,char* pat);

Void main()

{

char text[100], pattern[10];

printf("\nInput text:\n");

Gets(text);

Do

{

Fflush(stdin);

printf("\nInput pattern:\n");

Gets(pattern);

if (pattern[0] == '.') break;

if (pattern[0] == '?') {printf("\n%s",text); continue; }

if (FindKMP(text, pattern)) printf("\n TRUE");

else printf("\n FALSE");

} while (1);

}

O(m) F[i]<= F[i-1] – (число операций на i-м шаге) + 1

while len i=2,...,m,

сm, с – константа.

Алгоритм Боуера-Мура

х d_х

Hoola–Hoola girls like Hooligans.

Hooliga n

Hooliga n

Hooliga n

Hooliga n

Hooligan

#include <string.h>

#include <stdio.h>

#define ASIZE 256

int BM(char* text, char *pattern, int n, int m)

{

Int i;

int d[ASIZE];

//preprocessing...

for (i=0;i<ASIZE;i++) d[i] = m + 1;

for (i=0;i<m;i++) d[pattern[i]] = m - i;

//actual search...

i = 0;

while (i <= n - m)

{

printf("%s\n",&text[i]);

if (memcmp(&text[i],pattern,m) == 0) return i+1;

i = i + d[text[i + m]];

}