4. Листинг программы

//Подключаемые библиотеки и функции

#include <locale.h>

#include <iostream>

using namespace std;

int DirectSearch(char *string, char *substring, int &Sdvig1);

int KMPSearch(char *string, char *substring, int &Sdvig1);

int BMSearch(char *string, char *substring, int &Sdvig1);

//Функция-процедура main()

int main(int argc, char **argv)

{

char str[100];

char substr[100];

int k = 1;

int n = 400;

cout << "k = " << k << endl;

cout << "n = " << n << endl;

int Sdvig = 0;

setlocale( 0, "" ); cout << "Введите строку в которой будет производиться поиск: " << endl; setlocale(LC_CTYPE, ".OCP");

cin >> str;

setlocale( 0, "" ); cout << "Введена строка: " << endl; setlocale(LC_CTYPE, ".OCP");

cout << "str = " << str << endl << endl;

setlocale( 0, "" ); cout << "Введите искомую подстроку: " << endl; setlocale(LC_CTYPE, ".OCP");

cin >> substr;

setlocale( 0, "" ); cout << "Введена подстрока: " << endl; setlocale(LC_CTYPE, ".OCP");

cout << "substr = " << substr << endl << endl;

setlocale( 0, "" ); cout << "Прямой метод поиска: " << endl; setlocale(LC_CTYPE, ".OCP");

n = DirectSearch(str, substr, Sdvig);

if ( n == -1 )

{

setlocale( 0, "" ); cout << "Не найдена подстрока в строке: " << endl ; setlocale(LC_CTYPE, ".OCP");

}

else

{setlocale( 0, "" ); cout << "Найден номер n начала подстроки в строке n = " << n << endl; setlocale(LC_CTYPE, ".OCP");};

{setlocale( 0, "" ); cout << "Количество сдвигов = " << Sdvig << endl<< endl << endl; setlocale(LC_CTYPE, ".OCP");};

setlocale( 0, "" ); cout << "Поиск методом Кнута, Морриса и Пратта: " << endl; setlocale(LC_CTYPE, ".OCP");

n = KMPSearch(str, substr, Sdvig);

if ( n == -1 )

{setlocale( 0, "" ); cout << "Не найдена подстрока в строке: " << endl ; setlocale(LC_CTYPE, ".OCP");}

else

{setlocale( 0, "" ); cout << "Найден номер n начала подстроки в строке n = " << n << endl; setlocale(LC_CTYPE, ".OCP");};

{setlocale( 0, "" ); cout << "Количество сдвигов = " << Sdvig << endl<< endl; setlocale(LC_CTYPE, ".OCP");};

setlocale( 0, "" ); cout << "Поиск методом Бойера и Мура: " << endl; setlocale(LC_CTYPE, ".OCP");

n = BMSearch(str, substr, Sdvig);

if ( n == -1 )

{setlocale( 0, "" ); cout << "Не найдена подстрока в строке: " << endl; setlocale(LC_CTYPE, ".OCP");}

else

{setlocale( 0, "" ); cout << "Найден номер n начала подстроки в строке n = " << n << endl; setlocale(LC_CTYPE, ".OCP");};

{setlocale( 0, "" ); cout << "Количество сдвигов = " << Sdvig << endl<< endl; setlocale(LC_CTYPE, ".OCP");};

return EXIT_SUCCESS;

}

//Функция-процедура прямого поиска подстроки в строке

int DirectSearch(char *string, char *substring, int &Sdvig1)

{

int Sdvig=0;

int i, j;

int sl, ssl;

int res = -1;

sl = strlen(string);

ssl = strlen(substring);

for (i = 0; i < sl - ssl + 1; i++)

{

for (j = 0; j < ssl; j++)

if ( substring[j] != string[i+j] ) break;

if ( j == ssl )

{ res = i; break;}

Sdvig++;

}

Sdvig1 = Sdvig;

return res;

}

// Функция-процедура алгоритма Кнута, Морриса и Пратта

int KMPSearch(char *string, char *substring, int &Sdvig1){

int Sdvig=0;

int sl, ssl;

int res = -1;

sl = strlen(string);

ssl = strlen(substring);

//Вычисление префикс функции

int i, j = 0, k = -1;

int *d;

d = new int[1000];

d[0] = -1;

while ( j < ssl - 1 )

{

while ( k >= 0 && substring[j] != substring[k] )

k = d[k];

j++;

k++;

if ( substring[j] == substring[k] )

d[j] = d[k];

else

d[j] = k;

}

//Поиск первого вхождения подстроки в строку

i = 0;

j = 0;

while ( j < ssl && i < sl )

{

while ( j >= 0 && string[i] != substring[j] )

{

j = d[j];

Sdvig++;

};

i++;

j++;

}

Sdvig1 = Sdvig;

delete [] d;

res = j == ssl ? i - ssl : -1;

return res;

}

// Функция-процедура алгоритма Бойера и Мура

int BMSearch(char *string, char *substring, int &Sdvig1)

{

int Sdvig=0;

int sl, ssl;

int Posl, Pos2;

int res = -1;

sl = strlen(string);

ssl = strlen(substring);

int j;

int i, Pos;

int BMT[256];

int BMS[100];

int p[100];

int p1[100];

// Вычисление таблицы стоп-символов (BMT)

for ( i = 0; i < 256; i ++ ) BMT[i] = ssl;

for ( i = ssl-2; i >= 0; i-- )

if ( BMT[(unsigned char)substring[i]] == ssl )

BMT[(unsigned char)substring[i]] = ssl - i - 1;

// Вычисление префикс функции (р) подстроки substring и префикс функции (р1) //обращения подстроки substring необходимые для вычисления таблицы суффиксов

p[0] = 0; // для префикса из нуля и одного символа функция равна нулю

p1[0] = 0;// для префикса из нуля и одного символа функция равна нулю

int k = 0;

int k1 = 0;

for(int i = 1; i < ssl; i++)

{

k1 = p1[i-1];

if (substring[ssl-1-k1] == substring[ssl-1-i])

{k1++; p1[i] = k1;}

else

{

if (k1>0) k = p1[k1-1]; else k=0;

if ( substring[ssl-1-k] != substring[ssl-1-i] ) k1 = 0; p1[i] = k1;

if ( substring[ssl-1-k] == substring[ssl-1-i] ) k1 = k+1; p1[i] = k1;

}

}

// Вычисление таблицы суффиксов (BMS)

for ( j = 0; j < ssl; j++ )

BMS[j]=ssl-p1[ssl-1];

for ( j = 0; j < ssl; j++ )

{ k = j;

while (( p1[k+1] < j) && (k+1 < ssl)) k++;

if (k < ssl) BMS[ssl-1-j] = k - p1[k]+1;

}

// Поиск

Pos = ssl - 1;

while ( Pos < sl )

{

j=ssl-1;

while (j >= 0)

{

if ( substring[j] == string[Pos-ssl+1+j] ) j--; else break;

};

if ( j == -1 ) {Sdvig1=Sdvig; return Pos-ssl+1;} else

{

if ( j == (ssl-1) ) Posl=Pos+BMT[(unsigned char)string[Pos]]; else Posl=1;

Pos2 = Pos+BMS[j+1];

Pos=max(Posl,Pos2);

Sdvig++;

};

}

Sdvig1=Sdvig;

return res;

}